【棧】逆波蘭計算器
2020-08-09 00:55:52
棧（stack）
- 棧是一個先進後出(FILO First In Last Out)的有序列表。
- 棧是限制線性表中元素的插入和刪除只能線上性表的同一端進行的一種特殊線性表。允許插入和刪除的一端， 爲變化的一端， 稱爲棧頂(Top), 另一端爲固定的一端， 稱爲棧底(Bottom)。
- 根據棧的定義可知，最先放入棧中元素在棧底，最後放入的元素在棧頂，而刪除元素剛好相反，最後放入的元素最先刪除，最先放入的元素最後刪除。
棧只有兩個操作：入棧（壓棧）和出棧
陣列模擬棧：
public class MyStack<E> {
private int size = 0;
private Object[] elementData;
public MyStack() {
elementData = new Object[10];
}
//入棧
public void push(E item) {
//判斷是否需要擴容
if (size - elementData.length >= 0) {
grow();
}
elementData[size++] = item;
}
// 檢視此堆疊頂部的物件，而不從堆疊中刪除它。
public E peek() {
if(size == 0) {
return null;
}
return (E) elementData[size - 1];
}
//出棧：刪除此堆疊頂部的物件，並將該物件返回。
public E pop() {
Object result = peek();
elementData[size - 1] = null;
size--;
return (E) result;
}
//判斷堆疊是否爲空
public boolean isEmpty() {
return size == 0;
}
//獲取堆疊的有效數據
public int size() {
return size;
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
}
//所有元素全部出棧並封裝在List中
public List<E> allPop() {
List<E> result = new ArrayList<E>();
for(int index = size - 1; index >= 0; index--) {
result.add((E) elementData[index]);
}
return result;
}
}
利用棧實現一個簡單計算器
只可以操作正整數的加、減、乘、除運算。
思路分析
- 利用兩個棧（運算元棧、操作符棧）
- 遇到運算元時：入運算元棧（需要注意的是：如果逐字元解析，那麼一個字元是運算元不能直接入棧，比如「76+2」，遇到字元7不能直接入棧，你需要入棧的是76。所以還需要判斷當前字元7的下一個是不是數位，如果是就需要拼接串，如果不是數位即是運算子，那麼就將當前拼的串轉爲int或long再入棧。而且在判斷下一個字元是不是運算元的時候還需要注意下標越界問題。如果當前字元已經是最後一個字元了那就可以入棧而無需判斷也判斷不了下一個）
- 遇到操作符時：如果當前操作符棧爲空，則直接入棧。 如果不爲空，則先判斷當前操作符與棧頂操作符的優先順序
- 如果當前操作符的優先順序小於或者等於棧頂操作符的優先順序則從運算元棧中彈出兩個數，操作符棧中出棧一個操作符，進行計算（這裏就是按照四則運算規則先計算優先順序高的，如果優先順序相同則按書寫順序計算。而且要特別注意的是 乘法和加法無所謂，但是除法和減法一定是 棧底元素除以或者減棧頂元素，因爲棧是先進後出的，所以按照我們的書寫規則，是被除數和被減數先進的棧）。然後將計算結果入運算元棧，將當前操作符入棧。
- 反之，操作符入棧。
- 最後如果操作符棧不爲空，那就將操作符棧中的運算子依次出棧計算。
注意在最後的計算中要保證操作符中棧頂的優先順序高於棧底的優先順序。 因爲永遠是先進行優先順序高的運算。
下面 下麪用剛纔實現好的計算器來模擬一下這個簡易的計算器：
public class MyCounter {
//用map來儲存運算子對應的優先順序
private static final Map<Character, Integer> priorityMap = new HashMap<>();
static {
priorityMap.put('+', 0);
priorityMap.put('-', 0);
priorityMap.put('*', 1);
priorityMap.put('/', 1);
}
//四則運算
private static int count(char c, int num1, int num2) {
int result = 0;
switch (c) {
case '*': result = num1 * num2; break;
case '/': result = num1 / num2; break;
case '+':result = num1 + num2; break;
case '-': result = num1 - num2; break;
}
return result;
}
//優先順序比較：0表示同等優先順序 1表示c1優先順序大於c2 -1表示c1優先順序小於c2
private static int comparePriority(char c1, char c2) {
int pc1 = priorityMap.get(c1);
int pc2 = priorityMap.get(c2);
return pc1 > pc2 ? 1 : (pc1 == pc2 ? 0 : -1);
}
//判斷是否爲操作符
private static boolean isOperator(char c) {
return c =='+' || c =='-' || c == '*' || c == '/';
}
//判斷是否爲運算元
private static boolean isNum(char c) {
return c >= '0' && c <= '9';
}
private static void dealOperator(MyStack<Integer> numStack, MyStack<Character> operatorStack, char c) {
if(operatorStack.isEmpty()) {
operatorStack.push(c);
return;
}
char c1 = operatorStack.peek();
int flag = 0;
//如果當前的操作符的優先順序小於或者等於堆疊中的操作符
if((flag = comparePriority(c, c1)) == 0 || flag == -1) {
int num1 = numStack.pop();
int num2 = numStack.pop();
int result = count(c1, num2, num1);
System.out.println(num2 + " " + c1 + " " + num1 + "的結果：" + result);
numStack.push(result);
operatorStack.pop();
operatorStack.push(c);
}else {
operatorStack.push(c);
}
}
//最後的計算操作
private static int dealLast(MyStack<Integer> numStack, MyStack<Character> operatorStack) {
while(!operatorStack.isEmpty()) {
char c = operatorStack.pop();
int num1 = numStack.pop();
int num2 = numStack.pop();
int result = count(c, num2, num1);
System.out.println(num2 + " " + c + " " + num1 + "的結果：" + result);
numStack.push(result);
}
return numStack.pop();
}
public static int executeCounter(String str) {
MyStack<Integer> numStack = new MyStack<Integer>();
MyStack<Character> operatorStack = new MyStack<Character>();
String numStr = "";
int len = str.length();
for(int index = 0; index < len; index++) {
char c = str.charAt(index);
if(isNum(c)) { //處理運算元
numStr += c;
//如果是運算元還需要往後面看一位，因爲可能是多位數。但是必須保證下標不越界
if(index < len - 1 && !isOperator(str.charAt(index + 1))) {
//如果不會越界而且不是操作符，那就拼接數位繼續掃描
continue;
}
//否則---運算元入棧,並且重置字串
numStack.push(Integer.parseInt(numStr));
numStr = "";
}else if(isOperator(c)) { //處理運算子
dealOperator(numStack, operatorStack, c);
}else {
throw new RuntimeException("非法字元");
}
}
//處理最後的計算
return dealLast(numStack, operatorStack);
}
}
測試：
public static void main(String[] args) {
String str = "5+70*2*2-5+1-5+3-4";
System.out.println("計算結果：" + MyCounter.executeCounter(str));
}
結果：
上述計算過程只有一個核心點：就是遇到一個運算子，先比較其與棧頂運算子的優先順序，如果前者低則計算，如果前者高則直接入棧，這保證了我們執行最終計算的時候是按照運算子優先順序由高到低的順序進行的；如果二者相等則計算，這保證優先順序相等的情況下按順序計算。
三種表達式求值
字首表達式（又稱波蘭式）：其實就是運算子位於運算元之前。
字首表達式的計算機求值：從右至左掃描表達式，遇到數位時，將數位壓入堆疊，遇到運算子時，彈出棧頂的兩個數，用運算子對它們做相應的計算(棧頂元素和次頂元素)，並將結果入棧;重複上述過程直到表達式最左端，最後運算得出的值即爲表達式的結果。例如：(3+4)*5-6對應的字首表達式是 - * + 3 4 5 6
中綴表達式：
中綴表達式就是常見的運算表達式，其實就是運算子位於兩運算數的中間，如（從左至右掃描）：(3+4)*5-6 的中綴表達式爲 3 + 4 * 5 - 6
中綴表達式的求值是我們人最熟悉的，但是對計算機來說卻不好操作，因此，在計算結果時，往往會將中綴表達式轉成其它表達式來操作(一般轉成後綴表達式)
後綴表達式（逆波蘭表達式）：運算子位於運算元之後
後綴表達式的計算機求值從左至右掃描表達式，遇到數位時，將數位壓入堆疊，遇到運算子時，彈出棧頂的兩個數，用運算子對它們做相應的計算(次頂元素和棧頂元素)，並將結果入棧;重複上述過程直到表達式最右端，最後運算得出的值即爲表達式的結果
例如: (3+4)*5-6對應的後綴表達式就是3 4 + 5 * 6 - ,針對後綴表達式求值步驟如下:
- 從左至右掃描， 將3和4壓入堆疊;
- 遇到+運算子， 因此彈出4和3 (4爲棧頂元素，3爲次頂元素)，計算出3+4的值，得7，再將7入棧;
- 將5入棧;
- 接下來是*運算子， 因此彈出5和7，計算出7X5=35，將35入棧;
- 將6入棧;
- 最後是-運算子，計算出35-6的值，即29， 由此得出最終結果。
我們在對後綴表達式求值時是非常容易的，只不過我們常人書寫的都是中綴表達式，所以人們提出了將中綴表達式轉爲後綴表達式的演算法（將中綴表達式轉換爲後綴表達式纔是重點）。這個演算法的具體描述如下：
中綴表達式轉爲後綴表達式：
- 初始化兩個棧: 運算子棧s1和儲存中間結果的棧s2;
- 從左至右掃描中綴表達式;
- 遇到運算元時，將其壓s2;
- 遇到運算子時，比較其與s1棧項運算子的優先順序:
- 如果s1爲空，或棧頂運算子爲左括號「("， 則直接將此運算子入棧;
- 否則，若優先順序比棧頂運算子的高，也將運算子壓入s1;
- 否則，將s1棧頂的運算子彈出並壓入到s2中，再次轉到(4.1)與s1中新的棧頂運算子相比較;
- 遇到括號時:
- 如果是左括號「("， 則直接壓入s1
- 如果是右括號「)」， 則依次彈出s1棧頂的運算子，並壓入s2，直到遇到左括號爲止，此時將這一對括號丟棄
- 重複步驟2至5，直到表達式的最右邊
- 將s1中 剩餘的運算子依次彈出並壓入s2
- 依次彈出s2中的元素並輸出，結果的逆序即爲中綴表達式對應的後綴表達式。
如果死記硬背那就扯淡了。不過通過閱讀人家設計出來的演算法，可以看出最終s1爲空，s2出棧的逆序爲逆波蘭表達式。我們對後綴表達式的操作是，遇到運算子之後彈出兩個運算元，執行運算計算出結果再壓棧，重複這種行爲，故可以看出：後綴表達式的每個運算子前面都要最起碼保證至少有兩個運算元。
可以看到在中綴轉後綴的時候總是從s1中往s2中「倒騰」東西，結合我們小學時候學的計算原則是先執行括號中的計算，然後按優先順序由高到低的順序先後 先後計算，如果運算級相同則按書寫順序計算。正是基於計算原則，所以他才需要這樣「倒騰」。其實我認爲可以分爲四種情形：
- 如果遇到右括號，s1則一直出棧併入到s2中，直到匹配到一個左括號爲止。因爲需要先執行括號內的計算，所以從s2的逆序看的話（後綴表達式計算），這樣保證了這個原則
- 如果新遇到的運算子優先順序比s1棧頂運算子的優先順序低，則s1棧頂運算子入到s2中，接着再用s1中新的棧頂運算子與當前這個運算子比較。這樣就保證了我們最終運算時永遠是先按照優先順序由高到低先後 先後執行的原則。
- 如果新遇到的運算子優先順序與s1棧頂運算子的優先順序相等，則s1棧頂運算子入到s2中，接着再用s1中新的棧頂運算子與當前這個運算子比較。這樣就保證了同等優先順序情況下，我們是按照運算子出現的順序（也就是書寫順序）計算的。
- 到最後，就s1而言，從棧頂到棧底，優先順序永遠是由高到低的。所以最終生成的後綴表達式正好可以讓我們先執行優先順序高的計算。
一箇中綴表達式轉爲後綴表達式的示意圖：
逆波蘭計算器的實現
只支援正整數運算。
其實跟上面的簡易計算器是一樣道理，只不過這個是先將中綴表達式轉換爲後綴表達式，然後再操作後綴表達式計算結果。
public class AgainstPoland {
private static final Map<Character, Integer> priorityMap = new HashMap<>();
static {
priorityMap.put('+', 0);
priorityMap.put('-', 0);
priorityMap.put('*', 1);
priorityMap.put('/', 1);
}
private static int comparePriority(char c1, char c2) {
int pc1 = priorityMap.get(c1);
int pc2 = priorityMap.get(c2);
return pc1 > pc2 ? 1 : (pc1 == pc2 ? 0 : -1);
}
private static boolean isOperator(char c) {
return c =='+' || c =='-' || c == '*' || c == '/';
}
private static boolean isNum(char c) {
return c >= '0' && c <= '9';
}
private static int count(char c, int num1, int num2) {
int result = 0;
switch (c) {
case '*': result = num1 * num2; break;
case '/': result = num1 / num2; break;
case '+':result = num1 + num2; break;
case '-': result = num1 - num2; break;
}
return result;
}
//中綴表達式轉換爲後綴表達式
public static String[] toInfixExpression(String str) {
MyStack<Character> s1 = new MyStack<Character>();
MyStack<String> s2 = new MyStack<String>();
int len = str.length();
String numStr = "";
for(int index = 0; index < len; index++) {
char c = str.charAt(index);
if(isNum(c)) {
numStr += c;
if(index < len - 1 && isNum(str.charAt(index + 1))) {
continue;
}
s2.push(numStr);
numStr = "";
}else if(isOperator(c)) {
dealOperator(s1, s2, c);
}else if(c == '(') {
s1.push(c);
}else if(c == ')') {
dealRightBracket(s1, s2);
}else {
throw new RuntimeException("非法字元");
}
}
//掃描完畢之後將s1中的運算子全部出棧並壓入到s2中
return dealLast(s1,s2);
}
private static void dealRightBracket(MyStack<Character> s1, MyStack<String> s2) {
//s1一直出棧並壓入到s2中，直到匹配到第一個‘（’
Character cTop;
while((cTop = s1.pop()) != '(') {
s2.push(cTop.toString());
}
}
private static void dealOperator(MyStack<Character> s1, MyStack<String> s2,char c) {
//如果棧爲空或者當前元素的優先順序高於棧頂運算子的優先順序-----直接入棧
if(s1.isEmpty() || s1.peek() =='(' || (comparePriority(c, s1.peek()) == 1)) {
s1.push(c);
}else {
/**
* 否則，就說明運算元棧不爲空，且當前元素的優先順序小於或等於棧頂運算子的優先順序
* 將s1中的棧頂運算子出棧並壓入s2中，再遞回比較
*/
s2.push(s1.pop().toString());
dealOperator(s1, s2, c);
}
}
private static String[] dealLast(MyStack<Character> s1, MyStack<String> s2) {
while(!s1.isEmpty()) {
s2.push(s1.pop().toString());
}
int size = s2.size();
String[] sArray = new String[size];
while(!s2.isEmpty()) {
sArray[--size] = s2.pop();
}
return sArray;
}
public static int executeCounter(String str) {
String[] sArray = toInfixExpression(str);
//後綴表達式求值
MyStack<Integer> tmpStack = new MyStack<Integer>();
String s;
char c;
int num1, num2;
for (int index = 0; index < sArray.length; index++) {
s = sArray[index];
c = s.charAt(0);
if(isOperator(c)) {
num1 = tmpStack.pop();
num2 = tmpStack.pop();
tmpStack.push(count(c, num2, num1));
continue;
}
tmpStack.push(Integer.parseInt(s));
}
return tmpStack.pop();
}
}
測試：
public static void main(String[] args) {
String str = "101+((21+3)*4)-5";
System.out.println(executeCounter(str));
}
輸出192