（詳細注釋）Java實作--表達式之中綴轉字尾并計算

    自打遇到棧，一直都想些寫一篇通俗易懂的将中綴表達式轉化為字尾表達式的博文，今天總算完成了這個心願。

    所有的解釋在代碼行裡面均有解釋。有什麼不懂的可以在評論區或者私信我。

    為了不用一直拉動代碼行看注釋（這回很麻煩也很浪費時間），本人将較長的注釋分成了兩行。

寫在前面：

      字尾表達式：波蘭逆序數，将中綴表達式轉換成字尾表達式不用做算數運算，它不求中綴表達式的值，隻是把操作數和操作符重新排列成另一種形式：字尾表示法。然後再求字尾表達式的結果。在解析表達式的時候，我們是将運算操作符存放在一個棧裡，*/的優先級要比+-高，但是如果+或者-在括号裡面，那麼它的優先級就要比* /要高。

定義棧代碼：

（對棧還不夠了解的，可以看我的另一篇博文）

https://blog.csdn.net/szlg510027010/article/details/82696158

  轉換代碼：

/**
 * 将中綴表達式轉化為字尾表達式
 * @author Administrator
 *
 */
public class InToPost {
	private String input;
	private String output="";
	private StackX theStack;
	
	public InToPost(String in) {
		input = in;
		int stackSize = input.length();
		theStack = new StackX(stackSize);
	}
	
	public String doTrans() {
		//利用for循環，讀取中綴表達式中的每一個字元
		for(int i=0;i<input.length();i++) {
		//定義一個字元型變量ch，将中綴表達式的字元賦給ch
			char ch = input.charAt(i);
		//演繹字元ch是否入棧，将棧中的内容先列印出來
			theStack.diaplayStack("For "+ch+" ");
		//利用switch-case語句，對應字元對應不同的操作
			switch(ch) {
			case '(':
		//如果ch是'('的話，直接将該字元壓入棧中
				theStack.push(ch);
				break;
				
		//如果ch是')'的話，執行gotParen操作，Paren是parenthesis的縮寫，
		//表示括号的意思，這裡即要實作擷取')'括号相對應的操作
			case ')':
				gotParen(ch);
				break;
		
		//如果ch是'+'或者'-'的話，擷取操作Oper是Operation的縮寫，即操作的意思
			case '+':
			case '-':
				gotOper(ch,1);
				break;
			
		//如果ch是'*'或者'/'，執行gotOper方法
			case '*':
			case '/':
				gotOper(ch,2);
				break;
				
		//如果擷取的字元既不是+-*/，也不是'('或者')'，表示這個字元是數字，直接指派給output.
			default:
				output+=ch;
				break;
		}
	}
	//當執行玩上述操作以後，棧不為空，則将棧中的元素一一指派給output
	//什麼時候執行完上述操作棧依然不為空呢？有很多例子，比如說(A+B)*C
	//在(A+B)*C中最後的時候棧中還會有*這個符号，因為我們在ch在==')'的時候
	//就把棧中裡面的内容'+'和'('[注意這裡是有順序的，先執行'+']給執行了，在遇到'('的時候
	//直接pop，其實質是将top--，'('它本身還在數組裡頭，這在我們初步學習棧的時候就已經說明過了
	//此時top==-1.相當于棧是空的
	//遇到'*'以後，将其壓入棧中
	//因為'*'後面已經沒有其它操作符[+-*/)(]，是以'*'就一直儲存在棧中了
		while(!theStack.isEmpty()) {
			theStack.diaplayStack("While ");
			output+=theStack.pop();
		}
		theStack.diaplayStack("End ");
	//傳回output，此時已經完成了将中綴表達式轉化為字尾表達式
		return output;
}
	//當遇到'(''+''-'或者'*'/'的時候執行以下操作
	public void gotOper(char opThis,int prec1) {
	//隻要棧中不為空，就要将棧頂元素拿出來，
	//若是'('則放回，若是'+''-''*''/'就要和棧頂元素進行比較
		while(!theStack.isEmpty()) {
	//擷取棧頂元素
			char opTop = theStack.pop();
			
	//如果棧頂元素是'('，則将其放回棧中，因為有'('，
	//表示後面一定有運算操作是要先執行的，'('也可以是看做一個标志符，或者說是分割符
			if(opTop=='(') {
					theStack.push(opTop);
	//退出循環，繼續下一個字元的操作
					break;
			}//否則如果不是'('的話，執行下面操作
			else {
	//定義一個prec2，prec2代表的是棧頂元素，
	//目的是為了跟prec1進行比較，prec1表示的是要插入棧中元素
	//如果prec2>prec1的話表示棧頂元素的優先級比要插入棧中的元素優先級要大,
	//此時我們就應該将棧頂元素指派給output,比如棧頂元素opTop為'*'  opThis為'+'
	//如果prec2<prec1的話，表明棧頂元素的優先級要小于要插入棧中的優先級，
	//此時我們将opTop放回棧中，比如棧頂元素opTop為'+'  opThis為'*',剛好與上述情況相反
				int prec2;
				
				if(opTop=='+' || opTop=='-') {
					prec2 = 1;
				}else 
					prec2 = 2;	
				
				
				if(prec2<prec1) {
	//如果棧頂元素的優先級要小于要插入棧中的優先級，此時我們将opTop放回棧中
					theStack.push(opTop);
	//退出循環，繼續下一個字元的操作
					break;
				}else
	//如果棧頂元素的優先級要大，則将其指派給output
					output += opTop;
			}
		}
	//總結一下上述的操作，其實就是将棧頂元素取出來，然後考慮它是否應該放回到棧中，
	//放回棧中有兩種情況：
	//1、如果遇到'('，我們就将它放回棧中
	//2、如果棧頂元素opTop的優先級要比opThis的優先級藥效，我們将它（棧頂元素opTop）放回棧中
	//指派給output的情況隻有一種：
	//就是棧頂元素opTop的優先級要比opThis的要大，
	//此時我們直接将其指派給output，
	//因為優先級都比opThis要大了，我們當然要先執行該運算啊！
		
	//考慮完棧頂元素opTop是應該放回還是不放回以後，我們将opThis放到棧裡面去
		theStack.push(opThis);
		
		
	//注：此方法針對的符号是
	//'('		'+'		'-'		'*'		'/'，五個，
	//如果遇到的是')'，不執行該方法，執行的是下面的方法gotOparen
	}
	
	//如果遇到')'我們并不将')'壓入棧中，這時候考慮的是是否将棧中元素指派給output的問題了
	public void gotParen(char ch) { 
	//如果該棧不為空,為空的時候不可能（隻要不是故意的）出現')'，
	//因為在表達式裡面有')'理所當然就有'('
	//是以不應該為空，為空根本就麼有意義去讨論
	    while(!theStack.isEmpty()) {
	//擷取棧頂元素，隻要棧頂元素不是'('，
	//則我們将其指派給output，然後進行下一次操作，直到遇到'('為止
		char chx = theStack.pop();
		if(chx=='(') {
			break;
		}else {
			output += chx;
		}
	}
	}
}
           

測試代碼： 

/**
 * 測試轉換
 * @author Administrator
 *
 */
public class TestTrans {
	public static void main(String[] args) {
		int interAns = 0;
		String input = "3*(4+5)-6/(1+2)";
		System.out.println("字首表達式："+input);
		InToPost test = new InToPost(input);
		String output = test.doTrans();
		System.out.println("字尾表達式："+output);
		System.out.println("計算字尾表達式：--------");
		//定義一個新的棧，用于存放數字
		Stack2 newStack = new Stack2(output.length());
		//周遊output即字尾表達式，如果遇到數字則将其入棧
		//如果遇到的是操作符，則将緊挨操作符的前兩個數字進行運算
		for(int i=0;i<output.length();i++) {
			//擷取output中小标對應的字元
			char ch = output.charAt(i);
			//如果擷取的元素是數字，那麼将其用過相減轉化為int類型
			//然後将其放到入棧
			if(ch>='0'&&ch<='9') {
				int number=ch-'0';
				newStack.push(number);
				System.out.println(newStack.peekTop());
			}else {
				//擷取符号前面的兩個數字
				//在這裡一定要注意
				//num1和num2的順序，+、*無所謂，但是-、/有所謂
				int num2 = newStack.pop();
				int num1 = newStack.pop();
				switch(ch) {
				case '+':
					interAns = num1 + num2;
					break;
				case '-':
					interAns = num1 - num2;
					break;
				case '*':
					interAns = num1 * num2;
					break;
				case '/':
					interAns = num1 / num2;
					break;
				}
				//講運算的結果入棧，然後周遊下一個元素
				newStack.push(interAns); 
			}
		}
		//列印結果
		System.out.println("The Answer is:"+interAns);
	}
}
           

測試結果：

字首表達式：D*(A+B)*C

For D Stack (bottom-->top):

For * Stack (bottom-->top):

For ( Stack (bottom-->top):* 

For A Stack (bottom-->top):* ( 

For + Stack (bottom-->top):* ( 

For B Stack (bottom-->top):* ( + 

For ) Stack (bottom-->top):* ( + 

For * Stack (bottom-->top):* 

For C Stack (bottom-->top):* 

While Stack (bottom-->top):* 

End Stack (bottom-->top):

字尾表達式：DAB+*C*

計算結果：

字首表達式：3*(4+5)-6/(1+2)

字尾表達式：345+*612+/-

計算字尾表達式：--------

3

4

5

6

1

2

The Answer is:25