- 中缀、前缀、后缀表达式
对于一个人可识别的表达式：1+(2+3)*4-5
根据操作符的位置不同分为：
①中缀表达式：1+(2+3)*4-5
②前缀表达式：- + 1 * + 2 3 4 5
③后缀表达式：1 2 3 + 4 * + 5 -
前缀表达式和后缀表达式里面已经包含了计算顺序，因此不需要括号来确定优先级
- 中缀转前缀
2.1 中缀转前缀
①按运算符优先级对所有的运算单位加括号
((1+((2+3)*4))-5)
②将运算符移动到对应括号的前面
(- ( + 1( * ( + 2 3 ) 4 )) 5 )
③去掉括号，得到前缀表达式
-
- 1 * + 2 3 4 5
转换的计算机实现：
（1）表达式树
（2）栈
①两个栈，运算符栈S1、存储中间结果栈S2
②从右到左扫描表达式
③遇到操作数，压栈S2
④遇到运算符，比较其与S1栈顶运算符优先级
若S1为空，或栈顶为右括号 ')' ，则此运算符入栈S1
若优先级比栈顶运算符高或相等，则此运算符入栈S1
若比栈顶优先级低，将S1栈顶运算符出栈压到S2里面，然后继续与S1栈顶运算符比较。重复④
⑤遇到括号
右括号直接压入S1
左括号，则依次弹出S1栈顶运算符到S2，直到遇到右括号，此时将这一对括号丢弃
⑥重复直到表达式最左边
⑦将S1剩余运算符依次弹出压到S2
⑧依次弹出S2中元素，得到前缀表达式
1 string midexToPreex(string &preex)
2 {
3 set<char> ops = {'+','-','*','/'};
4 map<char,int> priority = {{'+',1},{'-',1},{'*',2},{'/',2}};
5 ostringstream strstream;
6 // string *res = new string();
7 stack<node> s1,s2;
8 int preex_len = preex.size();
9 struct node temp;
10 for(int i=preex_len-1;i>=0;--i) {
11 if(preex[i] == ' ' || preex[i] == '\t') {
12 continue;
13 }
14 else if((preex[i]>='0' && preex[i]<='9') || preex[i] =='.') { //遇到操作数
15 ostringstream strtmp;
16 stack<char> num_tmp;
17 if(preex[i] != '.') { //对于15. 这种数，去掉后面的点，看作int类型
18 num_tmp.push(preex[i]);
19 }
20
21 // strtmp<<preex[i];
22 for(int j=i-1;j>=0;j--) { //这里还需要修改
23 if(preex[j]>='0'&& preex[j]<='9' || preex[j] =='.') {
24 num_tmp.push(preex[j]);
25 // strtmp<<preex[j];
26 i--;
27 }
28 else if(preex[j] == ' ' || preex[j] == '\t') {
29 i--;
30 }
31 else {
32 break;
33 }
34 }
35 while(!num_tmp.empty()) {
36 strtmp<<num_tmp.top();
37 num_tmp.pop();
38 }
39 temp.num = strtmp.str();
40 temp.flag = true;
41 s2.push(temp);
42 }
43 else if(ops.find(preex[i]) != ops.end()) { //如果是运算符
44 if(s1.empty() || (!s1.top().flag && s1.top().op==')')) {
45 temp.flag = false;
46 temp.op = preex[i];
47 s1.push(temp);
48 }
49 else if(priority[preex[i]] >= priority[s1.top().op]) {
50 temp.flag = false;
51 temp.op = preex[i];
52 s1.push(temp);
53 }
54 else if(priority[preex[i]] < priority[s1.top().op]) {
55 while(!(s1.empty() || s1.top().op==')' || priority[preex[i]] >= priority[s1.top().op])) {
56 s2.push(s1.top());
57 s1.pop();
58 }
59 temp.flag = false;
60 temp.op = preex[i];
61 s1.push(temp);
62 }
63 }
64 else if(preex[i] == ')') {
65 temp.flag = false;
66 temp.op = preex[i];
67 s1.push(temp);
68 }
69 else if(preex[i] == '(') {
70 while(s1.top().op != ')') {
71 s2.push(s1.top());
72 s1.pop();
73 }
74 s1.pop();//丢弃右括号
75 //此左括号不作处理，相当于丢弃了
76 }
77 else {
78 break;
79 }
80 }
81 while(!s1.empty()) {
82 s2.push(s1.top());
83 s1.pop();
84 }
85 while(!s2.empty()) {
86 if(s2.top().flag) {
87 strstream<<s2.top().num<<" ";
88 }
89 else {
90 strstream<<s2.top().op<<" ";
91 }
92 s2.pop();
93 }
94 return strstream.str();
95 }
2.2 前缀表达式解析计算
①从右到左扫描表达式
②遇到数字，则数字压栈，遇到运算符，取出栈顶的两个数做运算：栈顶 op 次顶，结果入栈
③重复直到表达式最左侧
1 template<typename T>
2 T cal(T n1,T n2,char op)
3 {
4 T res;
5 switch(op) {
6 case '+':res=n1+n2;break;
7 case '-':res=n1-n2;break;
8 case '*':res=n1*n2;break;
9 case '/':res=n1/n2;break;
10 default:break;
11 }
12 return res;
13 }
14
15 int cal_prerc(string &preex)
16 {
17 int ex_size = preex.size();
18 set<char> ops = {'+','-','*','/'};
19 bool int_or_double = true; //true代表表达式中只有int
20 if(preex.find('.') != string::npos) {
21 int_or_double = false;
22 }
23 stack<int> int_stack;
24 stack<double> double_stack;
25 for(int i = ex_size-1;i>=0;i--) {
26 if(preex[i] == ' ') {
27 continue;
28 }
29 if(preex[i]>='0'&&preex[i]<='9') {
30 stringstream tmp;
31 stack<char> tmp_stack;
32 tmp_stack.push(preex[i]);
33 for(int j=i-1;j>=0;--j) {
34 if((preex[j]>='0'&&preex[j]<='9') || preex[j]=='.') {
35 tmp_stack.push(preex[j]);
36 i--;
37 }
38 else if(preex[j] == ' ') {
39 break;
40 }
41 }
42 while(!tmp_stack.empty()) {
43 tmp<<tmp_stack.top();
44 tmp_stack.pop();
45 }
46 string str_tmp = tmp.str();
47 if(int_or_double) {
48 int num;
49 tmp>>num;
50 int_stack.push(num);
51 }
52 else{
53 double num;
54 tmp>>num;
55 double_stack.push(num);
56 }
57 }
58 else{ //如果是运算符
59 if(int_or_double) {
60 int a = int_stack.top();
61 int_stack.pop();
62 int b = int_stack.top();
63 int_stack.pop();
64 int res = cal(a,b,preex[i]);
65 int_stack.push(res);
66 }
67 else {
68 double a = double_stack.top();
69 double_stack.pop();
70 double b = double_stack.top();
71 double_stack.pop();
72 double res = cal(a,b,preex[i]);
73 double_stack.push(res);
74 }
75 }
76 }
77 if(int_or_double) {
78 int result = int_stack.top();
79 cout<<"result:"<<result<<endl;
80 }
81 else {
82 double result = double_stack.top();
83 cout<<"result:"<<result<<endl;
84 }
85 return 1;
86 }
- 中缀转后缀
3.1 中缀转后缀
①按运算符优先级对所有的运算单位加括号
②将运算符移动到对应括号的后面
③去掉括号，得到前缀表达式
（1）表达式树
（2）栈
3.2 后缀表达式解析结算
①从左到右扫描表达式
②遇到数字，数字压栈，遇到运算符，取出栈顶两个数做运算：次顶 op 栈顶，结果入栈
③重复，直到表达式最右侧
- 表达式合法性判断
（1）括号的合法性
这里的括号表达式只有 { } [ ] ( ) ，暂不算数字和运算符，且输入的表达式字符串里面没有其他无效字符
bool expreIsOK()
{
map<char,char> exmap = {{'}','{'},{']','['},{')','('}};
stack<char> char_stack;
string str;
getline(cin,str);
cout<<"Your expression:"<<str<<endl;
string::iterator iter = str.begin();
while(iter != str.end()) {
if(exmap.find(*iter) != exmap.end()) { //如果是右括号
if(char_stack.empty() || char_stack.top() != exmap[*iter]) {
return false;
}
else {
char_stack.pop();
}
}
else { //如果是左括号
char_stack.push(*iter);
}
++iter;
}
if(char_stack.empty()) {
return true;
}
else {
return false;
}
}
（2）运算符合法性
（3）运算数合法性
- 完整的解析计算中缀表达式
①检验合法性：包括括号的合法性和运算符的合法性、运算数合法性
括号合法性：括号成对出现且遵循数学规范
运算符合法性：比如不能有两个连续的运算符
运算数合法性：这里暂忽略大数。如果遇到小数，则运算数 3.14 5. 都是合法的，但 3.14. 不合法
②中缀转成前缀
③前缀解析计算
原文链接: https://www.cnblogs.com/taoXiang/p/12563477.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/194796
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
