1. 介绍

表达式分为前缀、中缀、后缀。前缀表达式，也称为波兰表达式，其特点是将操作符置于操作数的前面。后缀表达式，也成为逆波兰表达式，所有操作符置于操作数的后面。波兰表达式、逆波兰表达式均是由波兰数学家Jan Łukasiewicz所提出的。中缀表达式将操作符放在操作数中间。前缀表达式和后缀表达式相对于中缀表达式最大的不同是，去掉了表示运算优先级的括号。

1.1 前缀表达式求值

求值过程中会用到栈，用以存储操作数和中间运算结果。

从右至左扫描前缀表达式，进行如下操作：

（1）若遇到操作数，则操作数入栈；

（2）若遇到二元操作符，出栈两个元素；若是一元操作符，出栈一个元素；进行操作符对应的运算，将运算结果入栈；

直至扫描完整个表达式，最后栈中只有一个元素，即为表达式的值。

1.2 后缀表达式求值

与前缀表达式求值过程基本相同，不同的是从左至右扫描表达式。

1.3 中缀表达式求值

求值方法与下面的中缀转后缀的算法有点类似。中缀表达式有括号，并且操作符有运算优先级，求值过程中会用到两个栈：opnd栈和oprt栈。opnd栈用以存储操作数或中间运算结果，oprt栈用以存储操作符或'('。

从左至右扫描中缀表达式，每扫描到一个字符，做如下处理：

（1）若是操作数，则入opnd栈。

（2）若是操作符，则将其与oprt栈顶元素相比较，

①该操作符高于栈顶元素，说明该操作符的操作对象还没被扫描到，直接将该操作符压入oprt栈。

②该操作符的优先级低于oprt栈顶元素，说明该操作符前面的式子应该先运算。将oprt栈进行出栈操作直至该操作符的优先级高于栈顶元素（或栈顶元素为'('，或栈为空）。同时，opnd也对应地进行出栈操作，如果oprt栈顶元素是二元操作符，opnd出栈两个元素；如果oprt栈顶元素是一元操作符，opnd出栈一个元素；然后，进行相应的运算，将运算结果压入opnd栈。

（3）若遇到'('，直接将其压入oprt栈。

（4）若遇到')'，说明需要对该括号内的式子进行运算；oprt栈进行出栈操作直至栈顶元素是'('，并且在出栈的过程中做对应于oprt栈顶元素的运算，如（2）中②所描述。将运算结果压入opnd栈。

扫描完中缀表达式后，oprt进行出栈操作直至栈为空，并做对应于oprt栈顶元素的运算，将运算结果压入opnd栈。最后，opnd栈的栈顶元素即为中缀表达式的值。

2. 中缀与后缀之间的转换

2.1 中缀转后缀

将中缀表达式转换为后缀表达式的经典算法是Shunting yard算法（也叫调度场算法）[3]，由Dijkstra引入，因其操作类似火车编组场而得名。为了做简单的四则运算，这里将Shunting yard算法做了部分简化。

用栈存储操作符和左括号'('。

从左至右扫描中缀表达式，按如下情况进行处理：

（1）若遇到操作数，将操作数直接输出；

（2）若遇到操作符，有以下两类情况：

①操作符的运算优先级高于栈顶元素，表明该操作符的下一个操作对象还没被扫描到（针对的是二元操作符）；将该操作符压入栈。

②操作符的运算优先级低于或等于栈顶元素，表明该操作符的两个操作对象已经输出了；进行出栈操作直至该操作符优先级高于栈顶元素（或栈顶元素为'('，或栈为空）；然后，将该操作符压入栈。

（3）若遇到'('，直接将其压入栈；

（4）若遇到')'，表明该括号内的式子扫描完毕；进行出栈操作直至栈顶元素是'('，并且出栈的过程中输出栈顶元素（相当于打印括号内的操作符）。

当扫描到中缀表达式的结尾时，将栈中元素出栈并输出。所得到的输出结果为所转化的后缀表达式。

2. 2 后缀转中缀

以操作符为非叶节点、操作数为叶节点的二叉树，可以用来表示表达式，并且其前序、中序、后序遍历分别为该表达式的前缀、中缀、后缀表示法。表达式，无论是前缀、中缀或是后缀，可以确定唯一一棵与之对应的二叉树。这里，操作符均指二元：'+'，'-'，'*'，'/'。由此易知，每一个操作符有左子树和右子树。我们称左子树所对应的表达式（字符串的形式）为该操作符的左子串，与此相应地有右子串。

在中序遍历该二叉树时，遇到操作符时，对其子串是否加括号是一个非常棘手的问题，大概分四种情况考虑：

①若是'+'，其左右子串均不需加括号。

②若是'-'，仅需考虑其右子串是否加括号。如果右子串的根结点是'+'或'-'（也就是说右子串根结点的运算优先级与'-'的相等），则需加括号；若是'*'或'/'，则不需要加括号。

③若是'*'，需考虑左右子串是否加括号。如果右子串的根结点是'+'或'-'（也就是说左子串根结点的运算优先级小于'*'），则需加括号；若是'*'或'/'，则不需要加括号。同样地，对左子串的进行一样的处理。

④若是'/'，需考虑左右子串是否加括号。如果右子串的根结点是操作符，说明右子串是含有操作符的表达式，则需加括号。对左子串的处理方式与③相同，如果左子串的根结点是'+'或'-'（也就是说左子串根结点的运算优先级小于'/'），则需加括号；若是'*'或'/'，则不需要加括号。

所谓对子串加括号，是指在子串的末和尾分别加上'('和')'。

将后缀转中缀有两种方法：

方法一：由后缀表达式建立相应的二叉树，再对二叉树进行中序遍历，所得结果即为中缀表达式。

方法二：用栈来实现。有两个栈，一个是opnd栈，用以存储子串或操作数；另一个是oprt栈，用以存储是操作符的子串根节点，如果子串的根结点是操作数，不予存储。注意到，在扫描后缀表达式时，子串的根结点都是最后才被扫描到。所以，也可以说oprt栈存储的是子串的最后一个操作符。

从左至右扫描后缀表达式，

（1）若遇到操作数，直接入opnd栈。

（2）若遇操作符，从opnd栈取出两个子串，栈顶是该操作符的右子串，栈顶的下一个是该操作符的左子串；对oprt栈，如果左右子串含操作符（也就是子串长度大于1），栈顶是左子串的最后一个操作符，栈顶的下一个是右子串的操作符。如果子串的长度大于1，说明该子串含有操作符，oprt栈做出栈操作。

（3）按照上面提及的规则，做加括号的处理。

（4）处理之后，操作符入oprt栈；左子串+操作符+右子串，构成新的子串，入opnd栈。

3. Referrence

[1] 维基百科，波兰表示法。

[2] 维基百科，逆波兰表示法。

[3] 维基百科，Shunting yard算法。

[4]ssjhust123，中缀表达式转换为后缀表达式。

4. 问题

4.1 POJ 3295

题目大意：对波兰记法的前缀表达式，判断其是否为永真式。

有5个操作数p,q,r,s,and t，对应的取值情况有32种。为了取遍32种值，采用了网上代码的一个小技巧(i>>j)%2。

源代码：

3295

Accepted

184K

0MS

C++

1377B

2013-09-24 11:02:18

@H_301_795@#include<iostream> #include<cstring> #include<stack> using namespace std; stack<int>st; int val[5]; bool flag; char str[101]; void calculate(int len) { int i; int temp1,temp2; for(i=len-1;i>=0;i--) { switch(str[i]) { case 'K': { temp1=st.top(); st.pop(); temp2=st.top(); st.pop(); st.push(temp1&&temp2); break; } case 'A': { temp1=st.top(); st.pop(); temp2=st.top(); st.pop(); st.push(temp1||temp2); break; } case 'N': { temp1=st.top(); st.pop(); st.push(!temp1); break; } case 'C': { temp1=st.top(); st.pop(); temp2=st.top(); st.pop(); st.push(!temp1||temp2); break; } case 'E': { temp1=st.top(); st.pop(); temp2=st.top(); st.pop(); st.push(temp1==temp2); break; } default: st.push(val[str[i]-'p']); } } } int main() { int i,j,len; while (scanf("%s",&str)&&str[0]!='0') { len=strlen(str); flag=true; while(!st.empty()) //clear stack st.pop(); for(i=0;i<32;i++) { for(j=0;j<5;j++) val[j]=(i>>j)%2; calculate(len); if(!st.top()) { flag=false; break; } } if(flag) printf("tautology\n"); else printf("not\n"); } return 0; }

4.2 POJ 2106

题目大意：对中缀记法的的布尔表达式进行求值。

非运算'!'是一元运算，并且具有最高运算优先级。输入有诸如："!!!F"的，需要考虑清楚。

没考虑到"!!!F"，RE了一次；还有一些情况没考虑到，WA了几次。逻辑关系一定要理清楚。

源代码：

2106

Accepted

184K

0MS

C++

1801B

2013-09-30 17:56:35

@H_301_795@#include <iostream> #include <stack> #include <map> using namespace std; stack<char>oprt; stack<int>opnd; map<char,int>priority; int compute(int a,int b,char op) { if(op=='&') return a&&b; else if(op=='|') return a||b; } int evaluate(char *in) { int i,temp1,temp2; while(!oprt.empty()) oprt.pop(); while(!opnd.empty()) opnd.pop(); int len=strlen(in); for(i=0;i<len;i++) { if(in[i]==' ') continue; else if(isupper(in[i])) opnd.push(in[i]=='V'); else { switch(in[i]) { case '&': case '|': while(!oprt.empty()&&oprt.top()!='('&&priority[in[i]]<=priority[oprt.top()]) { temp1=opnd.top(); opnd.pop(); if(oprt.top()=='!') opnd.push((1+temp1)%2); else { temp2=opnd.top(); opnd.pop(); opnd.push(compute(temp2,oprt.top())); } oprt.pop(); } oprt.push(in[i]); break; case '!': case '(': oprt.push(in[i]); break; case ')': while(oprt.top()!='(') { temp1=opnd.top(); opnd.pop(); if(oprt.top()=='!') opnd.push((1+temp1)%2); else { temp2=opnd.top(); opnd.pop(); opnd.push(compute(temp2,oprt.top())); } oprt.pop(); } oprt.pop(); break; } } } while(!oprt.empty()) { temp1=opnd.top(); opnd.pop(); if(oprt.top()=='!') opnd.push((1+temp1)%2); else { temp2=opnd.top(); opnd.pop(); opnd.push(compute(temp2,oprt.top())); } oprt.pop(); } return opnd.top(); } int main() { int count=1; char in[150]; priority['|']=1; priority['&']=2; priority['!']=3; while(gets(in)) printf("Expression %d: %c\n",count++,evaluate(in)?'V':'F'); return 0; }

4.3 POJ 1686

题目大意：判断两个表达式是否相等。

思路：将变量的值带入计算：0~9按0~9处理，其他变量取ASCII码值。若两个表达式的值相等，即说明两个表达式相等；反之，则否。中缀表达式求值太麻烦了，先将其转化为后缀表达式，再求值。

不过，这种方法会误判式子a+d与b+c相等。不过，好在测试数据没这么BT。

写代码时，犯了好多低级错误。还有，scanf遇到空格、回车等会停止读取，结束这一次的输入。若输入的字符串带空格、tab的话，用gets。

源代码：

1686

Accepted

188K

0MS

C++

1815B

2013-09-25 17:32:35

@H_301_795@#include <iostream> #include <map> #include <stack> using namespace std; map<char,int>priority; /*transform the infix to the postfix*/ void transform(char *str) { stack<char>st1; int i,len; char temp[80]; len=strlen(str); while (!st1.empty()) st1.pop(); for(i=0,j=0;i<len;i++) { if(isalnum(str[i])) temp[j++]=str[i]; else { switch(str[i]) { case '+': case '-': case'*': while (!st1.empty()&&st1.top()!='('&&priority[str[i]]<=priority[st1.top()]) { temp[j++]=st1.top(); st1.pop(); } st1.push(str[i]); break; case '(': st1.push(str[i]); break; case ')': while (st1.top()!='(') { temp[j++]=st1.top(); st1.pop(); } st1.pop(); break; } } } while (!st1.empty()) { temp[j++]=st1.top(); st1.pop(); } temp[j]='\0'; strcpy(str,temp); } /*calculate the result of a postfix expression*/ int calculate(char *s,int len) { int i; int temp1,temp2; stack<int>st2; for(i=0;i<len;i++) { if(isdigit(s[i])) st2.push(s[i]-'0'); else if(isalpha(s[i])) st2.push(s[i]); else { temp1=st2.top(); st2.pop(); temp2=st2.top(); st2.pop(); switch(s[i]) { case '+': st2.push(temp1+temp2); break; case '-': st2.push(temp2-temp1); break; case '*': st2.push(temp1*temp2); break; } } } return st2.top(); } int main() { int N,result1,result2; char str1[80],str2[80]; priority['+']=1; priority['-']=1; priority['*']=2; scanf("%d",&N); getchar(); while (N--) { gets(str1); transform(str1);; result1=calculate(str1,strlen(str1)); gets(str2); transform(str2); result2=calculate(str2,strlen(str2)); if(result1==result2) printf("YES\n"); else printf("NO\n"); } return 0; }

4. 4 POJ 1400

题目大意：对中缀表达式去除多余的括号。

现将中缀转后缀，再将后缀转中缀。

调试、思考了一个晚上，一早起来灵感迸发，写出来了。

源代码：

1400

Accepted

256K

704MS

C++

2586B

2013-09-30 09:10:0

@H_301_795@#include<iostream> #include<string> #include <stack> #include <map> using namespace std; stack<char>oprt; stack<string>opnd; map<char,int>priority; string infix2postfix(string in) { int i; string post=""; while(!oprt.empty()) oprt.pop(); for(i=0;i<in.length();i++) { if(isalpha(in[i])) post+=in[i]; else { switch(in[i]) { case '+': case '-': case '*': case '/': while(!oprt.empty()&&oprt.top()!='('&&priority[in[i]]<=priority[oprt.top()]) { post+=oprt.top(); oprt.pop(); } oprt.push(in[i]); break; case '(': oprt.push(in[i]); break; case ')': while(oprt.top()!='(') { post+=oprt.top(); oprt.pop(); } oprt.pop(); break; } } } while(!oprt.empty()) { post+=oprt.top(); oprt.pop(); } return post; } string postfix2infix(string post) { int i; string temp1,temp2; char top_oprt,next_top; while(!oprt.empty()) oprt.pop(); while(!opnd.empty()) opnd.pop(); for(i=0;i<post.length();i++) { if(isalpha(post[i])) { temp1=""; temp1+=post[i]; opnd.push(temp1); } else { temp1=opnd.top(); opnd.pop(); temp2=opnd.top(); opnd.pop(); if(temp1.length()>1) { top_oprt=oprt.top(); oprt.pop(); } if(temp2.length()>1) { next_top=oprt.top(); oprt.pop(); } switch(post[i]) { case '-': if(temp1.length()>1&&priority[top_oprt]==priority['-']) //add parenthese { temp1.insert(0,"("); temp1.insert(temp1.length(),")"); } break; case '*': if(temp1.length()>1&&priority[top_oprt]<priority['*']) { temp1.insert(0,")"); } if(temp2.length()>1&&priority[next_top]<priority['*']) { temp2.insert(0,"("); temp2.insert(temp2.length(),")"); } break; case '/': if(temp1.length()>1) { temp1.insert(0,")"); } if(temp2.length()>1&&priority[next_top]<priority['/']) { temp2.insert(0,")"); } break; } oprt.push(post[i]); temp2+=post[i]; temp2+=temp1; opnd.push(temp2); } } return opnd.top(); } int main() { int N; string in,post; priority['+']=priority['-']=1; priority['*']=priority['/']=2; cin>>N; while(N--) { cin>>in; post=infix2postfix(in); in=postfix2infix(post); cout<<in<<endl; } return 0; }