前面我們介紹了三種數(shù)據(jù)結構，第一種數(shù)組主要用作數(shù)據(jù)存儲苍凛，但是后面的兩種棧和隊列我們說主要作為程序功能實現(xiàn)的輔助工具趣席，其中在介紹棧時我們知道棧可以用來做單詞逆序醇蝴，匹配關鍵字符等等秧倾，那它還有別的什么功能嗎魔种？以及數(shù)據(jù)結構與本篇博客的主題前綴屎蜓、中綴惫周、后綴表達式有什么關系呢？
1惭适、人如何解析算術表達式
如何解析算術表達式笙瑟？或者換種說法，遇到某個算術表達式腥沽，我們是如何計算的：
①逮走、求值 3+4-5
這個表達式，我們在看到3+4后都不能直接計算3+4的值，知道看到4后面的 - 號师溅，因為減號的優(yōu)先級和前面的加號一樣茅信，所以可以計算3+4的值了，如果4后面是 * 或者 /墓臭，那么就要在乘除過后才能做加法操作蘸鲸，比如：
②、求值 3+45*
這個不能先求3+4的值窿锉，因為4后面的*運算級別比前面的+高酌摇。通過這兩個表達式的說明，我們可以總結解析表達式的時候遵循的幾條規(guī)則：
①嗡载、從左到右讀取算式窑多。
②洼滚、已經(jīng)讀到了可以計算值的兩個操作數(shù)和一個操作符時埂息，可以計算，并用計算結果代替那兩個操作數(shù)和一個操作符遥巴。
∏Э怠③、繼續(xù)這個過程铲掐，從左到右拾弃，能算就算，直到表達式的結尾摆霉。
2豪椿、計算機如何解析算術表達式
對于前面的表達式 3+4-5，我們?nèi)耸怯兴季S能力的携栋，能根據(jù)操作符的位置砂碉，以及操作符的優(yōu)先級別能算出該表達式的結果。但是計算機怎么算刻两？
計算機必須要向前（從左到右）來讀取操作數(shù)和操作符，等到讀取足夠的信息來執(zhí)行一個運算時滴某，找到兩個操作數(shù)和一個操作符進行運算磅摹，有時候如果后面是更高級別的操作符或者括號時，就必須推遲運算霎奢，必須要解析到后面級別高的運算户誓，然后回頭來執(zhí)行前面的運算。我們發(fā)現(xiàn)這個過程是極其繁瑣的幕侠，而計算機是一個機器帝美，只認識高低電平，想要完成一個簡單表達式的計算晤硕，我們可能要設計出很復雜的邏輯電路來控制計算過程悼潭，那更不用說很復雜的算術表達式庇忌，所以這樣來解析算術表達式是不合理的，那么我們應該采取什么辦法呢舰褪？
請大家先看看什么是前綴表達式皆疹，中綴表達式，后綴表達式：這三種表達式其實就是算術表達式的三種寫法占拍，以 3+4-5為例
①略就、前綴表達式：操作符在操作數(shù)的前面，比如 +-543
②晃酒、中綴表達式：操作符在操作數(shù)的中間表牢，這也是人類最容易識別的算術表達式 3+4-5
③、后綴表達式：操作符在操作數(shù)的后面贝次，比如 34+5-
上面我們講的人是如何解析算術表達式的崔兴，也就是解析中綴表達式，這是人最容易識別的浊闪，但是計算機不容易識別恼布，計算機容易識別的是前綴表達式和后綴表達式，將中綴表達式轉換為前綴表達式或者后綴表達式之后搁宾，計算機能很快計算出表達式的值折汞，那么中綴表達式是如何轉換為前綴表達式和后綴表達式，以及計算機是如何解析前綴表達式和后綴表達式來得到結果的呢盖腿？
3爽待、后綴表達式
后綴表達式，指的是不包含括號翩腐，運算符放在兩個運算對象的后面鸟款，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行（不再考慮運算符的優(yōu)先規(guī)則）茂卦。
由于后綴表達式的運算符在兩個操作數(shù)的后面何什，那么計算機在解析后綴表達式的時候，只需要從左向右掃描等龙，也就是只需要向前掃描处渣，而不用回頭掃描，遇到運算符就將運算符放在前面兩個操作符的中間（這里先不考慮乘方類似的單目運算）蛛砰，一直運算到最右邊的運算符罐栈，那么就得出運算結果了。既然后綴表達式這么好泥畅，那么問題來了：
①荠诬、如何將中綴表達式轉換為后綴表達式？
對于這個問題，轉換的規(guī)則如下：
一柑贞、先自定義一個棧
package com.ys.poland;
public class MyCharStack {
private char[] array;
private int maxSize;
private int top;
public MyCharStack(int size){
this.maxSize = size;
array = new char[size];
top = -1;
}
//壓入數(shù)據(jù)
public void push(char value){
if(top < maxSize-1){
array[++top] = value;
}
}
//彈出棧頂數(shù)據(jù)
public char pop(){
return array[top--];
}
//訪問棧頂數(shù)據(jù)
public char peek(){
return array[top];
}
//查看指定位置的元素
public char peekN(int n){
return array[n];
}
//為了便于后面分解展示棧中的內(nèi)容方椎，我們增加了一個遍歷棧的方法(實際上棧只能訪問棧頂元素的)
public void displayStack(){
System.out.print("Stack(bottom-->top):");
for(int i = 0 ; i < top+1; i++){
System.out.print(peekN(i));
System.out.print(' ');
}
System.out.println("");
}
//判斷棧是否為空
public boolean isEmpty(){
return (top == -1);
}
//判斷棧是否滿了
public boolean isFull(){
return (top == maxSize-1);
}
}
二、前綴表達式轉換為后綴表達式
package com.ys.poland;
public class InfixToSuffix {
private MyCharStack s1;//定義運算符棧
private MyCharStack s2;//定義存儲結果棧
private String input;
//默認構造方法凌外，參數(shù)為輸入的中綴表達式
public InfixToSuffix(String in){
input = in;
s1 = new MyCharStack(input.length());
s2 = new MyCharStack(input.length());
}
//中綴表達式轉換為后綴表達式辩尊，將結果存儲在棧中返回，逆序顯示即后綴表達式
public MyCharStack doTrans(){
for(int j = 0 ; j < input.length() ; j++){
System.out.print("s1棧元素為：");
s1.displayStack();
System.out.print("s2棧元素為：");
s2.displayStack();
char ch = input.charAt(j);
System.out.println("當前解析的字符:"+ch);
switch (ch) {
case '+':
case '-':
gotOper(ch,1);
break;
case '*':
case '/':
gotOper(ch,2);
break;
case '(':
s1.push(ch);//如果當前字符是'(',則將其入棧
break;
case ')':
gotParen(ch);
break;
default:
//1康辑、如果當前解析的字符是操作數(shù)摄欲，則直接壓入s2
//2、
s2.push(ch);
break;
}//end switch
}//end for
while(!s1.isEmpty()){
s2.push(s1.pop());
}
return s2;
}
public void gotOper(char opThis,int prec1){
while(!s1.isEmpty()){
char opTop = s1.pop();
if(opTop == '('){//如果棧頂是'(',直接將操作符壓入s1
s1.push(opTop);
break;
}else{
int prec2;
if(opTop == '+' || opTop == '-'){
prec2 = 1;
}else{
prec2 = 2;
}
if(prec2 < prec1){//如果當前運算符比s1棧頂運算符優(yōu)先級高疮薇，則將運算符壓入s1
s1.push(opTop);
break;
}else{//如果當前運算符與棧頂運算符相同或者小于優(yōu)先級別胸墙，那么將S1棧頂?shù)倪\算符彈出并壓入到S2中
//并且要再次再次轉到while循環(huán)中與 s1 中新的棧頂運算符相比較；
s2.push(opTop);
}
}
}//end while
//如果s1為空按咒，則直接將當前解析的運算符壓入s1
s1.push(opThis);
}
//當前字符是 ')' 時，如果棧頂是'(',則將這一對括號丟棄励七，否則依次彈出s1棧頂?shù)淖址窍瑝喝雜2，直到遇到'('
public void gotParen(char ch){
while(!s1.isEmpty()){
char chx = s1.pop();
if(chx == '('){
break;
}else{
s2.push(chx);
}
}
}
}
三掠抬、測試
@Test
public void testInfixToSuffix(){
String input;
System.out.println("Enter infix:");
Scanner scanner = new Scanner(System.in);
input = scanner.nextLine();
InfixToSuffix in = new InfixToSuffix(input);
MyCharStack my = in.doTrans();
my.displayStack();
}
四吼野、結果
五、分析
②两波、計算機如何實現(xiàn)后綴表達式的運算瞳步？
package com.ys.poland;
public class CalSuffix {
private MyIntStack stack;
private String input;
public CalSuffix(String input){
this.input = input;
stack = new MyIntStack(input.length());
}
public int doCalc(){
int num1,num2,result;
for(int i = 0 ; i < input.length() ; i++){
char c = input.charAt(i);
if(c >= '0' && c <= '9'){
stack.push((int)(c-'0'));//如果是數(shù)字，直接壓入棧中
}else{
num2 = stack.pop();//注意先出來的為第二個操作數(shù)
num1 = stack.pop();
switch (c) {
case '+':
result = num1+num2;
break;
case '-':
result = num1-num2;
break;
case '*':
result = num1*num2;
break;
case '/':
result = num1/num2;
break;
default:
result = 0;
break;
}//end switch
stack.push(result);
}//end else
}//end for
result = stack.pop();
return result;
}
public static void main(String[] args) {
//中綴表達式：1*(2+3)-5/(2+3) = 4
//后綴表達式：123+*123+/-
CalSuffix cs = new CalSuffix("123+*523+/-");
System.out.println(cs.doCalc()); //4
}
}
4腰奋、前綴表達式
前綴表達式单起，指的是不包含括號，運算符放在兩個運算對象的前面劣坊，嚴格從右向左進行（不再考慮運算符的優(yōu)先規(guī)則）嘀倒，所有的計算按運算符出現(xiàn)的順序。
注意：后綴表達式是從左向右解析局冰，而前綴表達式是從右向左解析括儒。
①、如何將中綴表達式轉換為前綴表達式锐想？
②、計算機如何實現(xiàn)前綴表達式的運算乍狐？
參考文檔：http://blog.csdn.net/antineutrino/article/details/6763722/
參考書籍：《Java數(shù)據(jù)結構和算法》
