中缀表达式转化为后缀表达式的过程详解及其实现代码_中缀表达式转后缀表达式代码

中缀表达式和后缀表达式的概念

中缀表达式：操作符以中缀形式处于操作数的中间，例：1 + 2。

后缀表达式：将运算符写在操作数之后，例：12+。

一个表达式E的后缀形式可以如下定义：

1. 如果E是一个变量或常量，则E的后缀式是E本身。
2. 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。
3. 如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。

那么为什么要将中缀表达式变为后缀表达式呢？
与后缀表达式相比，中缀表达式不容易被计算机解析，后缀表达式更易于计算机计算。

中缀表达式转化为后缀表达式的过程

将一个中缀表达式转换为后缀表达式的一般算法：

首先需要分配一个栈，作为临时存储运算符的栈S（含一个结束符号）。

将 ‘#’ 入栈S，作为结束符号，然后从左至右开始扫描中缀表达式：

1. 若取出的字符是操作数，则加入后缀表达式
2. 若取出的字符是运算符：
   a. 若为’(’，入栈；
   b. 若为’)’，则依次把栈中的运算符加入后缀表达式，直到出现’)’，然后从栈中删除’(’；
   c. 若为除了括号之外的其他运算符，当其优先级高于栈顶的运算符时，直接入栈； 否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到遇到一个比它优先级低或遇到了一个左括号为止。

运算符的优先级如下表所示：
isp(in stack priority)是栈内优先级，icp(in coming priority)是栈外优先级

实例及详细过程

例一： 将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式。

所以，中缀表达式a+b-a*((c+d)/e-f)+g与之对应的后缀表达式为ab+acd+e/f-*-g+

例二： 将中缀表达式a/b+(c*d-e*f)/g转换成等价的后缀表达式

所以，中缀表达式a/b+(c*d-e*f)/g与之对应的后缀表达式为ab/cd*ef*-g/+

中缀表达式转换为后缀表达式的手工做法

以例2给出的中缀表达式为例，中缀表达式转换为后缀表达式的手工做法为：

1. 按照运算符的优先级对所有的运算单位加括号。 例二： ((a/b) + (((c*d) - (e*f))/g))
2. 把运算符号移动到对应括号的后面，然后去掉括号。例二： ((ab)/ (((cd)*(ef)*)-g)/+，去掉括号ab/cd*ef*-g/+

中缀表达式转换为后缀表达式的代码实现（字母表达式）

#include<bits/stdc++.h>
using namespace std;

//栈内优先级
int isp(char c){
    if(c == '#'){
        return 0;
    }else if(c == '('){
        return 1;
    }else if(c == '+' || c == '-'){
        return 3;
    }else if(c == '*' || c == '/'){
        return 5;
    }else if(c == ')'){
        return 6;
    }
}

//栈外优先级
int icp(char c){
    if(c == '#'){
        return 0;
    }else if(c == '('){
        return 6;
    }else if(c == '+' || c == '-'){
        return 2;
    }else if(c == '*' || c == '/'){
        return 4;
    }else if(c == ')'){
        return 1;
    }
}


int main(){
    string str;
    while(getline(cin,str)){
        stack<char> data;
        stack<char> op;
        op.push('#');
        str += '#';
        int index = 0;
        while(index < str.size()){
            if(isalpha(str[index])){
                data.push(str[index]);
                cout<<data.top()<<" "; //输出字母
                index++;
            }else{
                if(icp(str[index]) == isp(op.top())){
                    op.pop();
                    index++;
                }else if(icp(str[index]) > isp(op.top())){//运算符进栈
                    op.push(str[index]);
                    index++;
                }else{
                    if(op.top() == ')'){ //如果该运算符是右括号，则直接弹出
                        op.pop();
                    }else{
                        cout<<op.top()<<" "; //输出
                        op.pop();
                    }
                }
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67