後綴表達式，又稱逆波蘭式，指的是不包含括弧，運算符放在兩個運算對象的後面，所有的計算按運算符出現的順序，嚴格從左向右進行（不再考慮運算符的優先規則）。
基本介紹
- 中文名：後綴表達式
- 學科：數學
- 對象：運算符
- 別稱：後綴或者逆波蘭
計算,轉換,代碼,c++代碼,pascal代碼,Java代碼,求值,
計算
運用後綴表達式進行計算的具體做法：
建立一個棧S 。從左到右讀表達式，如果讀到運算元就將它壓入棧S中，如果讀到n元運算符(即需要參數個數為n的運算符)則取出由棧頂向下的n項按運算元運算，再將運算的結果代替原棧頂的n項，壓入棧S中 。如果後綴表達式未讀完，則重複上面過程，最後輸出棧頂的數值則為結束。
轉換
計算機實現轉換：
將中綴表達式轉換為後綴表達式的算法思想：
·開始掃描；
·數字時，加入後綴表達式；
·運算符：
a. 若為 '('，入棧；
b. 若為 ')'，則依次把棧中的運算符加入後綴表達式中，直到出現'('，從棧中刪除'(' ；
c. 若為 除括弧外的其他運算符， 當其優先權高於除'('以外的棧頂運算符時，直接入棧。否則從棧頂開始，依次彈出比當前處理的運算符優先權高和優先權相等的運算符，直到一個比它優先權低的或者遇到了一個左括弧為止，然後將其自身壓入棧中（先出後入）。
·當掃描的中綴表達式結束時，棧中的的所有運算符出棧；
人工實現轉換
這裡我給出一個中綴表達式：a+b*c-(d+e)
第一步：按照運算符的優先權對所有的運算單位加括弧：式子變成了：((a+(b*c))-(d+e))
第二步：轉換前綴與後綴表達式
前綴：把運算符號移動到對應的括弧前面
則變成了：-( +(a *(bc)) +(de))
把括弧去掉：-+a*bc+de 前綴式子出現
後綴：把運算符號移動到對應的括弧後面
則變成了：((a(bc)* )+ (de)+ )-
把括弧去掉：abc*+de+- 後綴式子出現
發現沒有，前綴式，後綴式是不需要用括弧來進行優先權的確定的。如表達式：3+(2-5)*6/3
後綴表達式 棧
3_________________+
3 ________________+(
3 2 _______________+(-
3 2 5 -_____________ +
3 2 5 - _____________+*
3 2 5 - 6 * ___________+/
3 2 5 - 6 *3 __________+/
3 2 5 - 6 *3 /+________
("_____"用於隔開後綴表達式與棧)
另外一個人認為正確的轉換方法:
遍歷中綴表達式的每個節點，如果：
1、 該節點為運算元：
直接拷貝進入後綴表達式
2、 該節點是運算符，分以下幾種情況：
A、 為“（”運算符：
壓入臨時堆疊中
B、 為“）”運算符：
不斷地彈出臨時堆疊頂部運算符直到頂部的運算符是“（”為止，從棧中刪除'('。並把彈出的運算符都添加到後綴表達式中。
C、 為其他運算符，有以下步驟進行：
比較該運算符與臨時棧棧頂指針的運算符的優先權，如果臨時棧棧頂指針的優先權大於等於該運算符的優先權，彈出並添加到後綴表達式中，反覆執行前面的比較工作，直到遇到一個棧頂指針的優先權低於該運算符的優先權，停止彈出添加並把該運算符壓入棧中。
此時的比較過程如果出現棧頂的指針為‘（’，則停止循環並把該運算符壓入棧中，注意：‘（’不要彈出來。
遍歷完中綴表達式之後，檢查臨時棧，如果還有運算符，則全部彈出，並添加到後綴表達式中。
代碼
c++代碼
#include <stack>#include <vector>#include <iostream>#include <algorithm>using namespace std;bool isOper(char c)//判斷是否為操作符{ if ((c == '+ ') || (c == '- ') || (c == '* ') || (c == '/ ') || (c == '( ') || (c == ') ')) return true; return false;}bool isHigh(char top_op, char InfixExp_op)//判斷操作符的優先權//top_op為棧頂操作符//InfixExp_op為當前讀入操作符//如果棧頂操作符優先權高，則彈出棧頂操作符//如果棧頂操作符優先權低，則壓入當前讀入操作符{ if ((top_op == '+ ') && (InfixExp_op == '+ ')) return true; if ((top_op == '+ ') && (InfixExp_op == '- ')) return true; if ((top_op == '- ') && (InfixExp_op == '+ ')) return true; if ((top_op == '- ') && (InfixExp_op == '- ')) return true; if ((top_op == '* ') && (InfixExp_op == '+ ')) return true; if ((top_op == '* ') && (InfixExp_op == '- ')) return true; if ((top_op == '* ') && (InfixExp_op == '* ')) return true; if ((top_op == '* ') && (InfixExp_op == '/ ')) return true; if ((top_op == '/ ') && (InfixExp_op == '+ ')) return true; if ((top_op == '/ ') && (InfixExp_op == '- ')) return true; if ((top_op == '/ ') && (InfixExp_op == '* ')) return true; if ((top_op == '/ ') && (InfixExp_op == '/ ')) return true; if (InfixExp_op == ') ') return true; return false;}void input(vector <char> *InfixExp){ char c; cin >> c; while (c != '$ ') { InfixExp->push_back(c); cin >> c; }}void output(vector <char> *postfixExp){ vector <char> ::iterator postfixExp_it;//後綴表達式疊代器 for (postfixExp_it = postfixExp->begin(); postfixExp_it != postfixExp->end(); postfixExp_it++) cout << *postfixExp_it << " "; cout << endl;}void output2(vector <char> *postfixExp)//不輸出括弧//如果表達式中括弧不配對//則可能有多餘的括弧未彈出{ vector <char> ::iterator postfixExp_it;//後綴表達式疊代器 for (postfixExp_it = postfixExp->begin(); postfixExp_it != postfixExp->end(); postfixExp_it++) { if ((*postfixExp_it != '( ') && (*postfixExp_it != ') ')) cout << *postfixExp_it << " "; } cout << endl;}void main(){ stack <char> mystack; vector <char> InfixExp;//中綴表達式 vector <char> ::iterator InfixExp_it;//中綴表達式疊代器 vector <char> postfixExp;//後綴表達式 do { cout << "Please input a formula, ended by $: " << endl; input(&InfixExp); //輸入表達式 output(&InfixExp); for (InfixExp_it = InfixExp.begin(); InfixExp_it != InfixExp.end(); InfixExp_it++) { if (!isOper(*InfixExp_it)) //運算元，直接輸出 postfixExp.push_back(*InfixExp_it); else //操作符 { if (mystack.empty()) //棧為空，壓入操作符 mystack.push(*InfixExp_it); else if (isHigh(mystack.top(), *InfixExp_it)) //棧頂操作符優先,比如棧頂為*,當前操作符為+，則彈出* { if (*InfixExp_it != ') ') //非閉括弧 //彈出棧中操作符直到棧頂運算元優先權低於當前讀入運算元 //壓入當前讀入操作符 { do { postfixExp.push_back(mystack.top()); mystack.pop(); } while ((!mystack.empty()) && (isHigh(mystack.top(), *InfixExp_it))); mystack.push(*InfixExp_it); } else //閉括弧 { while ((!mystack.empty()) && (mystack.top() != '( ')) //彈出直到開括弧 { postfixExp.push_back(mystack.top()); mystack.pop(); } if ((!mystack.empty()) && (mystack.top() == '( ')) mystack.pop(); //彈出開括弧 } } else if (!isHigh(mystack.top(), *InfixExp_it)) //中綴表達式中操作符優先 //比如棧頂為+,而當前讀入* { mystack.push(*InfixExp_it); //壓入當前讀入操作符 } } } while (!mystack.empty()) //把棧中剩餘的操作符依次彈出 { postfixExp.push_back(mystack.top()); mystack.pop(); } output2(&postfixExp); while (!mystack.empty()) mystack.pop(); InfixExp.clear(); postfixExp.clear(); //清空棧、中綴表達式和後綴表達式 } while (true);}pascal代碼
program p2_29;const max=100; op_set:set of char=['+','-','*','/']; letter:set of char=['0'..'9'];var expression,result:string; procedure sean(expression:string);var i,top1,top2:integer; ovs:array [1..max] of string[max]; ops:array [1..max] of char; f:array ['#'..'/','#'..'/'] of shortint;begin f['+','+']:=1; f['+','-']:=1; f['+','*']:=-1; f['+','/']:=-1; f['+','(']:=-1; f['+',')']:=1; f['+','#']:=1; f['-','+']:=1; f['-','-']:=1; f['-','*']:=-1; f['-','/']:=-1; f['-','(']:=-1; f['-',')']:=1; f['-','#']:=1; f['*','+']:=1; f['*','-']:=1; f['*','*']:=1; f['*','/']:=1; f['*','(']:=-1; f['*',')']:=1; f['*','#']:=1; f['/','+']:=1; f['/','-']:=1; f['/','*']:=1; f['/','/']:=1; f['/','(']:=-1; f['/',')']:=1; f['/','#']:=1; f['(','+']:=-1; f['(','-']:=-1; f['(','*']:=-1; f['(','/']:=-1; f['(','(']:=-1; f['(',')']:=0; f['(','#']:=2; f[')','+']:=2; f[')','-']:=2; f[')','*']:=2; f[')','/']:=2; f[')','(']:=2; f[')',')']:=2; f[')','#']:=2; f['#','+']:=-1; f['#','-']:=-1; f['#','*']:=-1; f['#','/']:=-1; f['#','(']:=-1; f['#',')']:=2; f['#','#']:=0; {優先權設定} expression:=expression+'#';{末尾加標誌} ops[1]:='#'; top1:=0; top2:=1; for i:=1 to length(expression) do {逐個掃描} begin if expression[i] in letter then {是數字就進棧} begin inc(top1); ovs[top1]:=expression[i]; end else begin {運算符} while f[ops[top2],expression[i]]=1 do {棧頂運算符優先權高於當前運算符} begin {取棧頂上面的兩個元素運算後，再壓棧} ovs[top1-1]:=ovs[top1-1]+ovs[top1]+ops[top2]; top1:=top1-1; dec(top2); end; if f[ops[top2],expression[i]]=0 then top2:=top2-1 {優先權相同，則抵消} else {棧頂運算符優先權低於當前運算符，則壓棧} begin top2:=top2+1; ops[top2]:=expression[i]; end; end; end; result:=ovs[1];{返回結果}end;begin readln(expression); sean(expression); writeln(result); readln;Java代碼
/** * 後序遍歷遞歸實現 * * 左 右 中 * @param node */ public void nextOrder(Node node) { if (node == null) { return; } nextOrder(node.left); nextOrder(node.right); System.out.println(node.data); } /** * 後序遍歷非遞歸實現 * @param node */ public void nextOrder2(Node node) { if (node == null) { return; } Stack<Node> stack = new Stack<>(); Node p = node; while (node != null) { while (node.left != null) { stack.push(node); node = node.left; } while (node != null && (node.right == null || node.right == p)) { System.out.println(node.data); p = node; if (stack.isEmpty()) { return; } node = stack.pop(); } stack.push(node); node = node.right; } } 求值
後綴表達式的求值 pascal
註：輸入時符號和數字要空一格
program p2_30a;const maxn=20;var stack:array [1..maxn] of integer; s:string; function comp(s:string):integer;var ch:char; i,top,x,y,z:integer;begin top:=0; i:=1; ch:=s[i]; while i<=length(s) do {逐個位數判斷} begin case ch of '0'..'9':begin x:=0; while (ch<>' ') do begin x:=x*10+ord(ch)-ord('0'); {當前數位} i:=i+1; ch:=s[i];{下一位} end; inc(top); stack[top]:=x; end; '+':begin x:=stack[top]; dec(top); y:=stack[top];{獲得兩個數} z:=y+x; {計算} stack[top]:=z; {存值} end; '-':begin x:=stack[top]; dec(top); y:=stack[top];{獲得兩個數} z:=y-x; {計算} stack[top]:=z; {存值} end; '*':begin x:=stack[top]; dec(top); y:=stack[top];{獲得兩個數} z:=y*x; {計算} stack[top]:=z; {存值} end; '/':begin x:=stack[top]; dec(top); y:=stack[top];{獲得兩個數} z:=y div x; {計算} stack[top]:=z; {存值} end; end; inc(i); ch:=s[i]; end; exit(stack[top]);end;begin readln(s); writeln(comp(s)); readln;end.