精华内容
下载资源
问答
  • 假设存在后缀表达式abcd-*+ef/-,如何只借助结构将其转化为前缀表达式? 后缀表达式转前缀表达式规则: 从左到右扫描后缀表达式: 如果是操作数,则直接将其指针压入栈中 如果是操作符,则依次弹出两个栈顶指针...

    假设存在后缀表达式abcd-*+ef/-,如何只借助栈结构将其转化为前缀表达式?
    后缀表达式转前缀表达式规则:

    从左到右扫描后缀表达式:

    1. 如果是操作数,则直接将其指针压入栈中
    2. 如果是操作符,则依次弹出两个栈顶指针进行字符串拼接后,再和操作符进行拼接,返回新的指针压入栈中(先弹出的拼接在后弹出的后面,操作符拼接在最前面)
    3. 直到扫描结束,将栈顶指针弹出,即为前缀表达式字符串的指针

    我们可以先从数学模型上入手,理解为先:

    img

    于是我们就得到了abcd-*+ef/-的前缀表达式为-+a*b-cd/ef

    接下来我们开始代码实现,将这一数学模型转化为切实可行的程序。就像你学到了一种撩妹套路,也得应用到实际当中才算是真的掌握了。比如说,你晚上想约心仪的女生出来校园走走,你学到了这样一句话,“出来看星星吗?不看星星出来也行“。听着好像不错,但你得说给女生听,看看行不行得通,理论上是可以的,如果没有效果,那就是你个人的魅力问题了。

    核心算法函数:

    char* Algo(char *c)
    {
        char *s,*e1,*e2;
        int i;
        SqStack S;
    
        InitStack_Sq(&S);
    
        //Scan the suffix string from left to right
        for(i=0; c[i]; i++)
        {
            s = charToStr(c[i]);    //Transform the character to string array
            if(!isalpha(c[i]))      //If it's operator
            {
                Pop_Sq(&S, &e1);
                Pop_Sq(&S, &e2);
                s = mergeStr(s, mergeStr(e2, e1));  //Merge the string array ordered by operator, e2 and e1
            }
            Push_Sq(&S, s);
        }
    
        Pop_Sq(&S, &s);
        if(IsEmpty(S))
            return s;
        return NULL;
    }
    

    完整代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <string.h>
    
    #define STACK_INIT_SIZE 100
    #define STACK_INCREMENT 10
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    typedef char* SElemType_Sq; //Be careful: we need to memory the pointer of an array
    typedef struct
    {
        SElemType_Sq *base;
        SElemType_Sq *top;
        int stacksize;
    }SqStack;
    
    Status InitStack_Sq(SqStack *S);
    Status Push_Sq(SqStack *S, SElemType_Sq e);
    Status Pop_Sq(SqStack *S, SElemType_Sq *e);
    Status IsEmpty(SqStack S);
    char* charToStr(char c);
    char* mergeStr(char *a, char *b);
    char* Algo(char *c);
    
    int main()
    {
        char *c = "abcd-*+ef/-";
        char *s;
        s = Algo(c);
    
        printf("Prefix expression is: ");
        printf(s);
    
        return 0;
    }
    
    char* Algo(char *c)
    {
        char *s,*e1,*e2;
        int i;
        SqStack S;
    
        InitStack_Sq(&S);
    
        //Scan the suffix string from left to right
        for(i=0; c[i]; i++)
        {
            s = charToStr(c[i]);    //Transform the character to string array
            if(!isalpha(c[i]))      //If it's operator
            {
                Pop_Sq(&S, &e1);
                Pop_Sq(&S, &e2);
                s = mergeStr(s, mergeStr(e2, e1));  //Merge the string array ordered by operator, e2 and e1
            }
            Push_Sq(&S, s);
        }
    
        Pop_Sq(&S, &s);
        if(IsEmpty(S))
            return s;
        return NULL;
    }
    
    Status InitStack_Sq(SqStack *S)
    {
        S->base = (SElemType_Sq *)malloc(STACK_INIT_SIZE * sizeof(SElemType_Sq));
        if(!S->base) return ERROR;
        S->top = S->base;
        S->stacksize = STACK_INIT_SIZE;
    
        return OK;
    }
    
    Status Push_Sq(SqStack *S, SElemType_Sq e)
    {
        if(S->top - S->base >= S->stacksize)
        {
            S->base = (SElemType_Sq *)realloc(S->base, (S->stacksize+STACK_INCREMENT)*sizeof(SElemType_Sq));
            if(!S->base) return ERROR;
            S->stacksize += STACK_INCREMENT;
        }
        *(S->top) = e;
        S->top++;
    
        return OK;
    }
    Status Pop_Sq(SqStack *S, SElemType_Sq *e)
    {
        if(S->base == S->top) return ERROR;
        S->top--;
        *e = *(S->top);
    
        return OK;
    }
    
    Status IsEmpty(SqStack S)
    {
        if(S.base == S.top) return TRUE;
    
        return FALSE;
    }
    
    char* charToStr(char c)
    {
        char *s;
    
        s = (char *)malloc(2 * sizeof(char));
        if(!s) return NULL;
        s[0] = c;
        s[1] = '\0';
    
        return s;
    }
    
    
    char* mergeStr(char *a, char *b)
    {
        int alen,blen;
        char *s;
        int i,j;
    
        alen = strlen(a);
        blen = strlen(b);
    
        s = (char *)malloc((alen+blen+1) * sizeof(char));
        if(!s) return NULL;
    
        j = 0;
        //Put the array a into array s
        for(i=0; i<alen; i++)
            s[j++] = a[i];
    
        //Put the array b into array s after array a
        for(i=0; i<blen; i++)
            s[j++] = b[i];
    
        s[j] = '\0';
    
        return s;
    }
    
    
    展开全文
  • #include #include #define MAXSIZE 50 using namespace std;... cout 后缀表达式为:" ; } int main() { cout 请输入表达式:"; char str[55] = {0}; cin >> str; toSuff(str); return 0; }
    #include <iostream>
    #include <string>
    #define MAXSIZE 50
    using namespace std;
    
    struct Stack
    {
        char *ch;
        int top;
    };
    
    void InitStack(Stack &p)
    {
        p.ch = new char[MAXSIZE];
        if (!p.ch)
        {
            return;
        }
        for (int i = 0; i < MAXSIZE; i++)
        {
            p.ch[i] = '\0';
        }
        p.top = 0;
    }
    
    void PushStack(Stack &p, char e) 
    {
        if (p.top >= MAXSIZE)
        {
            return;
        }
        p.ch[p.top] = e;
        p.top++;
    }
    
    void PopStack(Stack &p, char &e)
    {
        if (p.top == 0)
        {
            return;
        }
        e = p.ch[p.top-1];
        p.top--;
    }
    
    void getTop(Stack p, char &e)
    {
        if (p.top == 0)
        {
            e = '@';
            return;
        }
        e = p.ch[p.top-1];
    }
    
    bool isEmpty(Stack p) 
    {
        if (p.top > 0)
        {
            return false;
        }
        return true;
    }
    
    
    void toSuff(char *p) 
    {
        Stack chS, numS;
        InitStack(chS);
        InitStack(numS);
        for (int i = 0; i < strlen(p); i++)
        {
            if (p[i] >= '0' && p[i] <= '9')
            {
                PushStack(numS, p[i]);
                continue;
            }
            else 
            {
                if (p[i] == '(')
                {
                    PushStack(chS, p[i]);
                    continue;
                }
    
                if (p[i] == ')')
                {
                    char temp;
                    for (int j = 0; j < chS.top; j++)
                    {
                        getTop(chS, temp);
                        if (temp != '(')
                        {
                            char t;
                            PopStack(chS, t);
                            PushStack(numS, t);
                        }
                        else
                        {
                            char t;
                            PopStack(chS, t);
                            break;
                        }
                    }
                    continue;
                }
    
                char s;
                getTop(chS, s);
                if (s == '@' || s == '(')//插入第一个
                {
                    PushStack(chS, p[i]);
                    continue;
                }
                if (s == '+' || s == '-')
                {
                    PushStack(chS, p[i]);
                    continue;
                }
    
                if ((s == '*' || s == '/' ) && (p[i] == '-' || p[i] == '+'))
                {
                    char temp;
                    //这里要先将chS的个数保存起来,不然进入下面循环时删掉了元素导致chS.top也变小了
                    //导致循环提早结束,不能把chS中的元素全部取出来
                    int num = chS.top;
                    for (int j = 0; j < num; j++)
                    {
                        getTop(chS, temp);
                        if (temp == '(')
                        {
                            break;
                        }
                        PopStack(chS, temp);
    
                        PushStack(numS, temp);
                    }
                    PushStack(chS, p[i]);
                }
    
            }
        }
        for (int i = 0; i <= chS.top; i++)
        {
            char t;
            PopStack(chS, t);
            PushStack(numS, t);
        }
        cout << "后缀表达式为:" << numS.ch;
    }
    
    int main() 
    {
        cout << "请输入表达式:";
        char str[55] = {0};
        cin >> str;
        toSuff(str);
    
    
        return 0;
    }
    
    展开全文
  • 前缀、中缀、后缀表达式 前缀表达式:/+A*BCD。 中缀表达式:A+B*C/D。 后缀表达式:ABC*+D/。 中缀表达式转换后缀表达式思路 操作数顺序不变,将运算符进行排序 将初始化为空栈; 从左到右扫描表达式的每...

    前缀、中缀、后缀表达式

    • 前缀表达式:/+A*BCD。
    • 中缀表达式:A+B*C/D。
    • 后缀表达式:ABC*+D/。

    中缀表达式转换后缀表达式思路

         操作数顺序不变,将运算符进行排序

    1. 将栈初始化为空栈;
    2. 从左到右扫描表达式的每一个字符,执行下面操作:

        2.1  遇到操作数:直接输出(添加到后缀表达式中)

        2.2  栈为空时,遇到运算符,直接入栈

        2.3  遇到左括号:将其入栈

        2.4  遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。

        2.5  遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈

        2.6  最终将栈中的元素依次出栈,输出。

    中缀转前缀表达式思路

    基本同以上相同,不同点:

    1、上面的从左到右扫描表达式,改成从右向左扫描每一个字符。

    2、左括号和右括号的判断和上面相反。

    代码演示:

    package com.arithmetic.learn.arith4.c1.chapter3;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class C1_3_10 {
    
        public static void main(String[] args) {
    
            String e = "20+5*(15-(9+1))/2";
            String resultPost = "20 5 15 9 1 + - * 2 / +";
            List<String> postFix = convert2Postfix(e);
            System.out.println(postFix);
            List<String> prefix = convert2Prefix(e);
            String resultPre = "+ 20 / * 5 - 15 + 9 1 2";
            System.out.println(resultPre);
        }
    
        private static List<String> convert2Prefix(String e) {
            List<String> items = convertStrToItems(e);
            List<String> prefix = convertToPrefix(items);
            return prefix;
        }
    
        private static List<String> convertToPrefix(List<String> items) {
            List<String> prefix = new ArrayList<>();
    
            Stack<String> stack = new Stack();
            for(int i = items.size()-1; i>= 0; i--){
                operate(items.get(i),stack,prefix);
            }
            while(!stack.isEmpty()){
                prefix.add(stack.pop());
            }
            return prefix;
        }
    
        private static List<String> convert2Postfix(String e) {
            List<String> items = convertStrToItems(e);
            List<String> posfix = convertToPostfix(items);
            return posfix;
        }
    
        private static List<String> convertToPostfix(List<String> items) {
            List<String> postfix = new ArrayList<>();
    
            Stack<String> stack = new Stack();
            for(String item : items){
                operate(item,stack,postfix);
            }
            while(!stack.isEmpty()){
                postfix.add(stack.pop());
            }
            return postfix;
        }
    
        private static void operate(String item,Stack<String> stack, List<String> postfix) {
            if(isOprator(item)){
                if(stack.isEmpty()){
                    stack.push(item);
                }else{
                    if(item.equals(")")){
                        //入栈
                        stack.push(item);
                    }else if(item.equals("(")){
                        //出栈输出,直至遇到(
                        String last = null;
                        while(!stack.isEmpty() && !( last = stack.pop()).equals("(")){
                            postfix.add(last);
                        }
                    }else{
                        if(isGE(stack.peek(),item)){
                            //弹出直至优先级大于前面的运算符,或前面是数字
                            String last = null;
                            while(!stack.isEmpty() && isGE((last = stack.pop()),item)){
                                postfix.add(last);
                            }
                            stack.push(last);
                            stack.push(item);
                        }else{
                            //入栈
                            stack.push(item);
                        }
                    }
                }
    
            }else{
                postfix.add(item);
            }
        }
    
        private static boolean isGE(String last, String item) {
            if(last.equals("+") || last.equals("-")){
                return item.equals("+") || item.equals("-");
            }else if(last.equals("*") || last.equals("/")){
                return true;
            }
            return false;
        }
    
        private static List<String> convertStrToItems(String e) {
            List<String> items = new ArrayList<>();
    
            String[] units = e.split("");
            int index = 0;
            for(String unit : units){
                if(isOprator(unit))  {
                    items.add(index++,unit);
                }else{
                    if(index == 0){
                        items.add(index++,unit);
                        continue;
                    }
                    String lastUnit = items.get(index-1);
                    if(isOprator(lastUnit)){
                        items.add(index++,unit);
                    }else{
                        items.remove(index-1);
                        items.add(index-1,lastUnit+unit);
                    }
                }
            }
            return items;
        }
    
        private static boolean isOprator(String unit) {
            return unit.equals("+") || unit.equals("-") || unit.equals("*") || unit.equals("/")
                    || unit.equals("(") || unit.equals(")");
        }
    }
    

     

    展开全文
  • 如果是数字就添加进栈,否则从里取出数字进行计算 else : operand2 = operandStack.pop() operand1 = operandStack.pop() result = doMath(token,operand1,operand2) operandStack.push(result) return ...

     

    class Stack:
        def __init__(self):
            self.items=[]
        def isEmpty(self):
            return self.items==[]
        def push(self,item):
            #添加元素进站
            self.items.append(item)
        def peek(self):
            #打印栈顶元素
            return self.items[len(self.items)-1]
        def pop(self):
            #从栈顶取出元素
            return self.items.pop()
        def size(self):
            #返回栈中元素的个数
            return len(self.items)
    
    def infixToPostfix(infixexpr):
        # prec字典存储着运算符的优先级
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        # 定义空栈存储运算符出栈和进栈操作结果
        openStack = Stack()
        # 存储最后的后缀表达式的结果list
        postficList = []
        # tokenList存储将表达式分割字符后的list,要求表达式中的字符之间必须有空格
        tokenList = infixexpr.split()
    
        for token in tokenList:
            # 只要分割的字符在A-Z或者阿拉伯数字0-9之间放到postficList
            if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token.isnumeric():
                #isnumeric()方法判断token是否是数字
                postficList.append(token)
                # 左括弧匹配
            elif token == '(':
                openStack.push(token)
            elif token == ')':
                toptoken = openStack.pop()
                # 非括弧符号匹配
                while toptoken != '(':
                    postficList.append(toptoken)
                    toptoken = openStack.pop()
            else:
                # 运算符优先级比较
                while (not openStack.isEmpty()) and (prec[openStack.peek()] >= prec[token]):
                    postficList.append(openStack.pop())
                openStack.push(token)
        while not openStack.isEmpty():
            postficList.append(openStack.pop())
    
        return " ".join(postficList)
    
    def postfixEval(postfixExpr):
        #后缀表达式的计算
        operandStack=Stack()
        tokenList=postfixExpr.split()
        #对表达式进行分离
        for token in tokenList:
            if token.isnumeric():
                operandStack.push(int(token))
                #如果是数字就添加进栈,否则从栈里取出数字进行计算
            else:
                operand2=operandStack.pop()
                operand1=operandStack.pop()
                result=doMath(token,operand1,operand2)
                operandStack.push(result)
        return operandStack.pop()
    def doMath(op,op1,op2):
        if op=="*":
            return op1*op2
        elif op=="/":
            return op1/op2
        elif op=="+":
            return op1+op2
        else:
            return op1-op2
    
    
    if __name__ == '__main__':
        print(infixToPostfix("A * B + C * D"))
        print(infixToPostfix("( ( A * B ) + ( C * D ) )"))
        print(infixToPostfix("A + B * C + D"))
        print(infixToPostfix("( A + B ) * ( C + D )"))
        print(infixToPostfix("A * B + C * D"))
        print(infixToPostfix("83 * 9 + 4"))
    
        postresult=infixToPostfix("70 * 9 + 4")
        #print(postresult)
        print(postfixEval(postresult))
    View Code

     

    转载于:https://www.cnblogs.com/jzxs/p/11090723.html

    展开全文
  • 记忆口诀:中缀表达式转后缀表达式--》从左往右,依次输出操作数,遇到操作符入栈,按照优先级原则出入。 后缀表达式得出结果--》从左往右把操作数入栈,遇到操作符把临近栈顶的两个操作数弹出与操作符结合得出...
  • 3.中缀转后缀 JAVA中的实现 1.数组实现 定义类ArrayList,模拟 此类具有三个属性: private int maxSize; //大小 private int[] stack; //实现所用的数组 在构造方法中初始化 private int top=-1; //...
  • 实现后缀表达式转前缀表达式

    千次阅读 2018-01-14 15:42:23
    先看下面的图片,这是后缀表达式32/6*3-3+转前缀的过程 对于表达式:32/6*3-3+ 其前缀式为:+-*/32633 操作数的顺序不会改变,变的是运算符的顺序,并且在后缀式中,运算顺序从左往...
  • 应用:中缀转后缀,中缀转前缀

    千次阅读 多人点赞 2018-12-01 23:04:03
    2)如果遇到操作符,则我们将其放入到中,遇到左括号时我们也将其放入中。 3)如果遇到一个右括号,则将元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。 4)如果遇到任何...
  • 文章目录背景知识表达式转换问题(考研经典)一:手工转换(1)中缀转前缀和中缀转后缀(2)前缀转中缀和后缀转中缀二:用实现表达式转换(1)中缀转后缀(2)中缀转前缀 背景知识 中缀表达式:a+b 前缀表达式...
  • 求题目给出的前缀表达式后缀表达式的样子 分析: 看到这题,小编一开始想到的先是用结构完成,但在一番尝试后,我放弃了,泪崩。最后只好用树,发现如果用树的话会方便许多。下面,小编就来介绍一下如何用树...
  • 前缀_中缀_后缀表达式前缀_中缀_后缀表达式三种表达式转换方法前缀、后缀表达式原理的计算器求值中缀转后缀表达式代码实现思路代码实现后缀表达式实现简易整数计算器思想代码实现 前缀_中缀_后缀表达式 三种...
  • 前言 我们把平时所用的标准四则运算表达式,即1 + (( 2 + 3)* 4 ) – 5这样的表达式叫做中缀表达式。...接下来就介绍如何将中缀表达式转化为前缀后缀表达式,这里介绍的方法是利用辅助。 中缀表达式转为
  • 1 的基本介绍 1.1 stack性质 是一个先入后出(FILO)的有序列表 (stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 允许插入和删除的一端, 为变化的一端, 称为栈顶(Top),...
  • 中缀转后缀: 初始化s,s表示符号,用来存放中间符号 步骤: 从前往后依次循环处理每个字符 若当前字符为操作数(数字或字母),直接输出(后缀表达式中操作数顺序与原序相同) 若当前字符为运算符或括号,分...
  • 前缀表达式:op a b 中缀表达式:a op b 后缀表达式 a b op 1、对于计算单独的后缀表达式较为简单,从左到右,遇到数字将其压入栈内,遇到操作符从中取出两个数进行...中缀转后缀:(从左到右) 1、遇到...
  • 后缀:逆波兰式 1、中存符号 2、字母、数字直接打印 3、先进,再比较优先级,只有当比中前一个符号优先级高的情况下才走下去,否则弹出前一个符号,直至前一个符号的优先级小于这个符号,也即是连续弹...
  • 开篇语:继上两篇博客介绍在符号匹配和进制转换中的应用后,本篇博客讲介绍前缀、中缀、后缀转换中的应用。 1中缀、前缀后缀概念介绍 中缀:算术表达式如 B*C中,乘法运算符 *为两个操作数之间的中缀。 ...
  • 之前笔试中国电信IT研发中心的时候,遇到了几个前、中、后缀表达式的相互转换,当时忘得差不多了,今天好好把该方面的知识好好复习,并把相关代码和思路自己缕了一遍: 将中缀表达式转换为前缀表达式: 遵循以下...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 364
精华内容 145
关键字:

栈前缀转后缀