後綴表達式求值演算法
① 算數表達式求值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;
}