1. 前言

假設我們已經知道中綴表達式和后綴表達式的概念. 我們可以用符號棧來實現中綴表達式向后綴表達式的轉變.

2. 符號棧實現中綴表達式轉變為后綴表達式

(1). 思路

我們設計了可變字符串與符號棧. 如果傳入的字符串的字符是數字字符，則直接將該字符append到stringbuilder中. 如果該字符是符號字符，首先先判斷符號棧是否為空，如果為空，則直接將該字符壓棧，如果不為空，則需要將該字符與棧頂字符進行優先級比較.如果棧頂元素的優先級＞該字符，毫無疑問，直接將棧頂元素彈棧.如果棧頂元素與該元素優先級相等，由于計算的順序是從左到右，所以仍然需要將棧頂元素彈棧. 彈棧過程結束以后，需要將該字符壓棧.

(2). 解

//將中綴表達式轉變為后綴表達式
//目前只討論沒有小括號的情況
public class postfixexpr {public StringBuilder postfix(String s) throws Exception {//符號棧Deque<Character> deque = new LinkedList<>();StringBuilder str = new StringBuilder();int i = 0;for (; i < s.length(); i++) {char c = s.charAt(i);//如果該字符是數字字符, 那么將該字符加入到可變字符串if(isNumber(c)) {str.append(c);} else {//如果棧空, 則直接將該符號壓棧//如果不為空, 則將棧頂元素與該字符作比較//if棧頂元素優先級大于等于該元素, 全部彈棧if(deque.isEmpty()) {deque.push(c);} else {while(!deque.isEmpty() && priority(deque.peek()) >= priority(c)){str.append(deque.pop());}deque.push(c);}}}while(!deque.isEmpty()) {str.append(deque.pop());}return str;}//設計判斷符號優先級的函數private int priority(char c) throws Exception {if (c == '+' || c == '-') {return 1;} else if (c == '*' || c == '/') {return 2;} else {throw new Exception();}}private boolean isNumber(char c) {if (c == '+' || c == '-' || c == '*' || c == '/') {return false;}return true;}
}