后缀表达式求值算法
① 算数表达式求值c++
为了简化问题，关注算法，本文的讨论基于以下三点：
1. 只考虑 + - * / ( ) 这几个基本运算符，且是二元操作
2. 运算数只考虑 0-9，这10个简单的数，方便从string中取出来
3. 输入的表达式没有语法错误
【背景知识】
中缀表示法（Infix expression）：操作符位于两个操作数中间，算术表达式的常规表示法。只用于二元操作符的情况，而且需要用括号和优先规则排除多义性。(A+B)*C-D/(E+F)
前缀表示法（Prefix expression）：也叫波兰表示法，操作符写在操作数的前面。这种方法常用于编译器设计方面。-*+ABC/D+EF
后缀表示法（Postfix expression），逆波兰表示法，操作符位于操作数后面。这种方法使表达式求值很方便。AB+C*DEF+/-
前、后缀表示法的三个特征：
1. 操作数的顺序与等价的中缀表示法中操作数的顺序一致
2. 不需要括号
3. 操作符的优先级不相关
用二叉树来表示更直观，前、中、后缀表示法分别对应前序、中序、后序遍历得到的结果。
【算符优先法】
输入中缀表达式，直接求值。首先了解四则运算的规则：
（1） 先乘除，后加减
（2） 从左到右
（3） 先括号内，后括号外
根据以上3条规则，在运算的每一步，任意两个相继出现的算符optr1和optr2之间的优先关系有3种：
>：optr1的优先权高于optr2
=：optr1的优先权等于optr2
<：optr1的优先权低于optr2
下表定义了算符之间的优先级。竖：optr1，横：optr2。
+
-
*
/
(
)
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=
)
>
>
>
>
>
>
#
<
<
<
<
<
=
在表达式的两头，分别加个#符号，当##配对时，代表求值完成。
由规则（1），+ - 比* / 的优先权低；由规则（2），当optr1=optr2时，令optr1 > optr2；由规则（3），optr1为+ - * / 时的优先级低于 ( 高于 ) ，当optr1为 ( 时，优先级最低，optr1为 ) 时，优先级最高。
算法实现：使用两个栈，分别存放操作符和操作数。
1）置操作数栈为空，起始符#入运算符栈。
2）依次读入表达式中的每个字符，如是操作数，入操作数栈；如是运算符，和运算符栈顶符号比较优先权。直到表达式求值完毕，即##配对。
[cpp]view plain
boolIsOperator(charch)
{
if(ch=='+'||ch=='-'||
ch=='*'||ch=='/'||
ch=='('||ch==')'||ch=='#')
returntrue;
else
returnfalse;
}
//运算符的优先关系
//'+','-','*','/','(',')','#'
charOprRelation[7][7]={{'>','>','<','<','<','>','>'},//'+'
{'>','>','<','<','<','>','>'},//'-'
{'>','>','>','>','<','>','>'},//'*'
{'>','>','>','>','<','>','>'},//'/'
{'<','<','<','<','<','=',''},//'('
{'>','>','>','>','','>','>'},//')'
{'<','<','<','<','<','','='}};//'#'
intConvertToIndex(charopr)
{
intindex;
switch(opr)
{
case'+':
index=0;
break;
case'-':
index=1;
break;
case'*':
index=2;
break;
case'/':
index=3;
break;
case'(':
index=4;
break;
case')':
index=5;
break;
case'#':
index=6;
break;
}
returnindex;
}
charPrecede(charopr1,charopr2)
{
intindex1=ConvertToIndex(opr1);
intindex2=ConvertToIndex(opr2);
returnOprRelation[index1][index2];
}
intOperate(intopnd1,charop,intopnd2)
{
intret;
switch(op)
{
case'+':
ret=opnd1+opnd2;
break;
case'-':
ret=opnd1-opnd2;
break;
case'*':
ret=opnd1*opnd2;
break;
case'/':
ret=opnd1/opnd2;
break;
}
returnret;
}
//算符优先算法
intCaculateExpression(stringexp)
{
stack<char>optr;//只处理+-#/()运算
stack<int>opnd;//只处理0-9的整数运算
charch;
inti=0;
exp+="#";
optr.push('#');
ch=exp[i++];
//如果##配对，表达式求值完成
while(ch!='#'||optr.top()!='#')
{
if(!IsOperator(ch))
{
//操作数入栈
opnd.push(ch-'0');
ch=exp[i++];
}
else
{
//比较栈顶操作符和新取得的操作符的优先关系
switch(Precede(optr.top(),ch))
{
case'<'://栈顶优先权低
optr.push(ch);
ch=exp[i++];
break;
case'='://括号配对，栈顶括号弹出
optr.pop();
ch=exp[i++];
break;
case'>'://栈顶优先权高，先弹出，计算，结果操作数入栈
charop=optr.top();
optr.pop();
intnum2=opnd.top();//第二个操作数在前
opnd.pop();
intnum1=opnd.top();
opnd.pop();
intret=Operate(num1,op,num2);
opnd.push(ret);
break;
}
}
}//endofwhile
//操作数栈的唯一元素即为计算结果
returnopnd.top();
}
boolPrior(charoptr1,charoptr2)
{
boolprior=false;
if(optr1=='*'||optr1=='/')
if(optr2=='+'||optr2=='-')
prior=true;
returnprior;
}
//前缀表达式->后缀表达式
stringPrefixToPostFix(stringexp)
{
stringpostRet;
stack<char>optr;
inti=0;
charch;
while(i<exp.length())
{
ch=exp[i++];
if(IsOperator(ch))
{
switch(ch)
{
case'(':
optr.push(ch);
break;
case')':
//将栈中最近的一个左括号之上的操作符全部弹出，添加到结果
while(optr.top()!='(')
{
postRet+=optr.top();
optr.pop();
}
optr.pop();//丢弃左括号
break;
case'+':
case'-':
case'*':
case'/':
//弹出操作符，直到栈为空，或遇到左括号，或优先级较低的操作符
//或者统一优先级的右结合操作符
while(!optr.empty()&&Prior(optr.top(),ch))
{
postRet+=optr.top();
optr.pop();
}
optr.push(ch);
break;
}
}
else
{
postRet+=ch;
}
}
//到达字符串末尾，弹出所有操作符，添加到结果
while(!optr.empty())
{
postRet+=optr.top();
optr.pop();
}
returnpostRet;
}
//前缀表达式->后缀表达式，再求值
intCaculateExpression_2(stringpostExp)
{
//先转换成后缀表达式
stringexp=PrefixToPostFix(postExp);
stack<int>opnd;
inti=0;
charch;
while(i<exp.length())
{
ch=exp[i++];
if(IsOperator(ch))
{
intnum2=opnd.top();
opnd.pop();
intnum1=opnd.top();
opnd.pop();
//计算结果并入栈
intret=Operate(num1,ch,num2);
opnd.push(ret);
}
else
{
//操作数入栈
opnd.push(ch-'0');
}
}
returnopnd.top();
}
【前缀->后缀表达式】
1）操作符栈为空，结果字符串为空。
2）依次读入中缀表达式的每个字符
-如是操作数，添加到结果字符串
-如是左括号，入操作符栈
-如是右括号，弹出栈内符号，添加到结果字符串，直到遇到栈内的左括号。弹出左括号。
-如是操作符，弹出栈内符号，添加懂啊结果字符串，直到遇到左括号，或优先级较低的操作符，或统一优先级的右结合符号。此操作符入栈
3）如到达字符串末尾，弹出所有栈内符号，添加到结果字符串
[cpp]view plain
【后缀表达式求值】
1）初始化操作数栈
2）从左到右依次读入后缀表达式的每个字符，如是操作数，入栈；如是操作符，弹出两个操作数，计算，结果入栈，直到表达式末尾。栈中的唯一数即是结果。注意弹出的第一个操作数是位于运算符右边的数。
[cpp]view plain
【二叉树法】
可以根据前缀表达式，构造出二叉树，后序遍历即得到后缀表达式。
【手动方法】
(A+B)*C-D/(E+F)
1）按照运算符优先级对所有运算单位加括号。(((A+B)*C）-(D/(E+F)))
2）前缀：把运算符移动到对应的括号前面：-(*(+(AB)C)/(D+(EF)))，再去掉括号：-*+ABC/D+EF
3）后缀：把运算符移动到对应的括号后面：(((AB)+C)*(D(EF)+)/)-，再去掉括号：AB+C*DEF+/-
② 数学表达式转换成后缀式(逆波兰式),对后缀式进行计算,
中缀表达式如1*2+(2-1), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程中写的表达式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两个操作数取出, 进行操作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式
1*2+(2-1), 就变为12*21-+;
后缀表达式中不含有括号, 且后缀表达式的操作数和中缀表达式的操作数排列次序完全相同, 只是运算符的次序发生了改变。我们实现的时候，只需要用一个特定工作方式的数据结构（栈），就可以实现。
其中stack op;用来存放运算符栈。数组ans用来存放后缀表达式。
算法思想：
从左到右扫描中缀表达式，是操作数就放进数组ans的末尾。
如果是运算符的话，分为下面3种情况：
1）如果是‘（’直接压入op栈。
2）如果是‘）’，依次从op栈弹出运算符加到数组ans的末尾，知道遇到'（'；
3) 如果是非括号，比较扫描到的运算符，和op栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符
则，把运算符压入栈。否则的话，就依次把栈中运算符弹出加到数组ans的末尾，直到遇到优先级低于扫描
到的运算符，并且把扫描到的运算符压入栈中。
就这样依次扫描，知道结束为止。
如果扫描结束，栈中还有元素，则依次弹出加到数组ans的末尾，就得到了后缀表达式。
我空间里面有详细介绍，中缀转换后缀的代码和问题描述，主要是理解算法的思想，和数据结构，这样才算掌握了。
http://hi..com/huifeng00/blog/item/70cb280dabd9d4216059f3d1.html
③ java后缀表达式实现表达式求值
import java.util.Scanner;
import java.util.Stack;
public class 表达式计算 {
private static Stack<String> num = new Stack<String>();//存后缀表达式
private static Stack<String> sign = new Stack<String>();//存入符号
private static Stack<Integer> result = new Stack<Integer>();//放结果
public static void getGroup(String line){//讲字符串转换为后缀表达式
for(int i=0; i<line.length(); i++){
char c = line.charAt(i);
if((int)c>=48 && (int)c<=57){//当遇到数字的时候,判断是不是多位数，然后在push进num
int j = i+1;
while(j<line.length() && (line.charAt(j)>=48 && line.charAt(j)<=57)){
j++;
}
num.push(line.substring(i, j));
i = j-1;
}else if(c == '('){//遇到左括号直接存进num
sign.push(String.valueOf(c));
}else if(c == ')'){//遇到右括号从sign中pop栈顶元素push到num知道遇到'(',然后再pop掉'('
while(!sign.peek().equals("(")){
num.push(sign.pop());
}
sign.pop();
}else{
int n = 0;
if(!sign.empty()){//如果sign中没有元素，直接令n = 0
n = getNum(sign.peek().charAt(0));
}
int m = getNum(c);
if(m >= n){//如果当前元素的运算级别比栈顶元素运算级别要高，就直接push进sign
sign.push(String.valueOf(c));
}else{
while(m < n){//如果当前运算运算级别比sign栈顶元素运算级别要低，就将sign栈顶元素pop并且push进num，知道不符合条件
num.push(sign.pop());//输入例子2*3+6/3的时候，这里一直报错
if(!sign.empty()){
n = getNum(sign.peek().charAt(0));
}else{
n = 0;
}
}
sign.push(String.valueOf(c));
}
}
}
while(!sign.empty()){
num.push(sign.pop());
}
}
private static int getNum(char c){
int n = 0;
switch(c){
case '+':
case '-':
n = 1;
break;
case '*':
case '/':
n = 2;
break;
}
return n;
}