详解如何将中缀表达式转化为后缀表达式

本文我将从两种角度来解析如何将中缀表达式转化为后缀表达式

一、从应对考试角度来（在最快的时间内得出最准确的答案）

首先我们应该知道，要想将中缀转化为后缀，需要借助堆栈实现。（不准备画图了，画图有点浪费时间）我会用最简单明了的语言使读者弄懂。[举个例子吧：比如将:2*（9+6/3-5）+4转化为后缀表达式2 9 6 3 / +5 – * 4 + ]

1、任何中缀表达式都由运算数，运算符，括号（大，中，小），这三部分组成。

2、从中缀表达式的左边开始扫描（脑中自己想像的），若遇到运算数时，则直接将其输出（不压入堆栈）。

3、若遇到左括号，则将其压栈。

4、若遇到右括号，表达括号内的中缀表达式已经扫描完毕。这时需将栈顶的运算符依次弹出并输出，直至遇到左括号[左括号弹出但不输出]。

5、若遇到的是运算符：a、如果该运算符的优先级大于栈顶运算符的优先级时，将其压栈

6、最后一步，若扫描到中缀表达式的末尾[即扫描结束]，若堆栈中还有存留的运算符依次弹出并输出即可。

肯定有一些读者还是没完全弄懂（毕竟全都是文字）。接下来，举一个例子：帮助大家消化

（1）out：2 stack：

（2）out：2 stack：*

（3）out：2 stack： * （

（4）out：2 9 stack ：* （

（5）out：2 9 stack ：* （ + 注：在堆栈中括号的优先级最低

（6）out：2 9 6 stack ：* （ +

（7）out ：2 9 6 stack ：* （ + /

（8）out ：2 9 6 3 stack ：* （ + /

（9）out ：2 9 6 3 / stack ：* （ +

（10）out： 2 9 6 3 / + stack : * (

（11）out：2 9 6 3 / + stack : * ( –

（12）out : 2 9 6 3 / + 5 stack : * （ – 遇到了右括号

（13）out：2 9 6 3 / + 5 – stack：* （

（14）out：2 9 6 3 / + 5 – stack：*

（15）out：2 9 6 3 / + 5 – stack ：* 括号弹出但不输出

（16）out ：2 9 6 3 / + 5 – * stack : 遇到了+

（17）out：2 9 6 3 / + 5 – * stack ：+

（18）out：2 9 6 3 / + 5 – * 4 stack : +

（19）out：2 9 6 3 / + 5 – * 4 + stack ：

终于结束了，写到我要吐。注：红笔标记的地方很重要，虽然步骤比较多，当是写起来非常快。至此第一种方法结束。接下来我会用程序实现将中缀表达式转化为后缀表达式，并通过后缀表达式来求值。

————————————————————————————————————————————

中缀转后缀表达式的代码如下：（注意代码实现的是多位整数的转化，没有实现小数的转化，通过多位整数的转化理解下原理，小数转化自然就

不难写了）

/* 中缀转后缀C++代码实现(比较方便) 1.遇到操作数：添加到后缀表达式中或直接输出 2.栈空时：遇到运算符，直接入栈 3.遇到左括号：将其入栈 4.遇到右括号：执行出栈操作，输出到后缀表达式，直到弹出的是左括号 注意：左括号不输出到后缀表达式 5.遇到其他运算符：弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈 6.将栈中剩余内容依次弹出后缀表达式 */ #include 
  
    #include 
   
     #include 
    
      #include 
      #include 
      
        #include 
       
         #define MAX 100 using namespace std; //设置优先级(注意默认操作数的优先级最高，即其不需要进栈，进栈的都是运算符) map 
        
          p; //一些初始化 struct Node{ double num;//操作数 char op;//操作符 bool flag;//true表示操作数，false表示操作符 }; typedef struct Node node; stack 
         
           s;//操作符栈 queue 
          
            q;//后缀表达式队列 // void change(string str){ node temp; for (int i = 0; i < str.length();){ if (str[i] == '('){//3.遇到左括号：将其入栈 temp.flag = false; temp.op = str[i]; s.push(temp); i++; }else if (str[i] == ')'){//4.遇到右括号：执行出栈操作，输出到后缀表达式，直到弹出的是左括号 while (!s.empty() && s.top().op != '('){ q.push(s.top()); s.pop(); } s.pop();//弹出左括号 i++; }else if (str[i] >= '0'&&str[i] <= '9'){ //如果是数字 temp.flag = true; temp.num = str[i] - '0'; i++;//后移一位,因为数字不一定是个位数 while (i < str.length() && str[i] >= '0'&&str[i] <= '9'){ temp.num = temp.num * 10 + (str[i] - '0'); i++; } q.push(temp);//操作数进入后缀表达式 }else{ //如果是操作符 //5.遇到其他运算符：弹出所有优先加大于或等于该运算符的栈顶元素，然后将该运算符入栈 temp.flag = false; while (!s.empty() && p[s.top().op]>=p[str[i]]){ q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } } //6.将栈中剩余内容依次弹出后缀表达式 while (!s.empty()){ q.push(s.top()); s.pop(); } } int main() { node cur; string str; p['+'] = p['-'] = 1;//通过hashmap赋值 p['*'] = p['/'] = 2; cin >> str; change(str); while (!q.empty()){ cur = q.front(); if (cur.flag == true) cout << cur.num<<" "; else cout << cur.op<<" "; q.pop(); } return 0; }

详解如何将中缀表达式转化为后缀表达式

后缀表达式求值代码（将之前的稍作修改了，添加了calculate函数来计算结果）

原理：从左到右扫描后缀表达式，如果是操作数，压栈，若是操作符，将弹出两个操作数，进行计算，计算的结果再压入栈中，最后栈顶的元素就是所要的值。

/* 中缀转后缀C++代码实现(比较方便) 1.遇到操作数：添加到后缀表达式中或直接输出 2.栈空时：遇到运算符，直接入栈 3.遇到左括号：将其入栈 4.遇到右括号：执行出栈操作，输出到后缀表达式，直到弹出的是左括号 注意：左括号不输出到后缀表达式 5.遇到其他运算符：弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈 6.将栈中剩余内容依次弹出后缀表达式 */ #include 
  
    #include 
   
     #include 
    
      #include 
      #include 
      
        #include 
       
         #define MAX 100 using namespace std; //设置优先级(注意默认操作数的优先级最高，即其不需要进栈，进栈的都是运算符) map 
        
          p; //一些初始化 struct Node{ double num;//操作数 char op;//操作符 bool flag;//true表示操作数，false表示操作符 }; typedef struct Node node; stack 
         
           s;//操作符栈 stack 
          
            s1;//存放操作数的，为了计算后缀表达式的值 queue 
           
             q;//后缀表达式队列 // //中缀转后缀函数 void change(string str){ node temp; for (int i = 0; i < str.length();){ if (str[i] == '('){//3.遇到左括号：将其入栈 temp.flag = false; temp.op = str[i]; s.push(temp); i++; } else if (str[i] == ')'){//4.遇到右括号：执行出栈操作，输出到后缀表达式，直到弹出的是左括号 while (!s.empty() && s.top().op != '('){ q.push(s.top()); s.pop(); } s.pop();//弹出左括号 i++; } else if (str[i] >= '0'&&str[i] <= '9'){ //如果是数字 temp.flag = true; temp.num = str[i] - '0'; i++;//后移一位,因为数字不一定是个位数 while (i < str.length() && str[i] >= '0'&&str[i] <= '9'){ temp.num = temp.num * 10 + (str[i] - '0'); i++; } q.push(temp);//操作数进入后缀表达式 } else{ //如果是操作符 //5.遇到其他运算符：弹出所有优先加大于或等于该运算符的栈顶元素，然后将该运算符入栈 temp.flag = false; while (!s.empty() && p[s.top().op] >= p[str[i]]){ q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } } //6.将栈中剩余内容依次弹出后缀表达式 while (!s.empty()){ q.push(s.top()); s.pop(); } } //* //后缀表达式的计算 /* 从左到右扫描后缀表达式 1）若是操作数，就压栈， 2）若是操作符，就连续弹出两个操组数 3）栈顶的值即为所需结果 注：先弹出的是第一操作数，后弹出的是第二操作数 */ double calculate(){ double num_a, num_b;//操作数a,b node cur, temp; while (!q.empty()){//后缀队列非空 cur = q.front();//记录队首元素 q.pop(); if (cur.flag == true){//是操作数进入栈 s1.push(cur); } else{//是操作符就运算 num_b = s1.top().num; s1.pop();//弹出第二操作数 num_a = s1.top().num; s1.pop();//弹出第一操作数 temp.flag = true; if (cur.op == '+'){ temp.num = num_a + num_b; } else if (cur.op == '-'){ temp.num = num_a - num_b; } else if (cur.op == '*'){ temp.num = num_a * num_b; } else{ temp.num = num_a / num_b; } s1.push(temp);//把计算后的结果再次压栈 } } return s1.top().num; } //* int main() { string str; p['+'] = p['-'] = 1;//通过hashmap赋值 p['*'] = p['/'] = 2; cin >> str; change(str); //* //中缀转后缀 /*while (!q.empty()){ cur = q.front(); if (cur.flag == true) cout << cur.num << " "; else cout << cur.op << " "; q.pop(); }*/ while (!s1.empty()){//初始化栈s1 s1.pop(); } double answer=calculate(); cout << answer<

详解如何将中缀表达式转化为后缀表达式