10--棧計算器（補充：前綴、中綴、后綴表達式規則；逆波蘭表達式計算器）

一、前綴表達式【波蘭表達式】：

1. 前綴表達式也稱為波蘭表達式，其特點是運算符位于操作數之前
2. 舉例說明：（3+4)*5-6 對應的前綴表達式就是：- * + 3 4 5 6

前綴表達式的計算機求值：

從右至左掃描表達式，遇到數字時，將數字壓入堆棧中，遇到運算符，彈出來棧頂的2個數，用運算符對他們做相應的運算（棧頂元素和次頂元素），并將結果入棧，重復上述過程直到表達式最左端，最后運算得出的值即為表達式的值，例如（3+4)*5-6 對應的前綴表達式就是：- * + 3 4 5 6，針對前綴表達式求值步驟如下：

1. 從右至左掃描，將6、5、4、3壓入堆棧
2. 遇到 + 運算符，因此彈出3（棧頂元素）、4（次頂元素），計算出3+4=7，將7入棧
3. 接下來是 * 運算符，因此彈出7和5，計算出7*5=35，將35入棧
4. 最后是 - 運算符，計算出 35 - 6 = 29【先彈出來的 - 后彈出來的】，將29入棧 

二、中綴表達式：

1. 中綴表達式就是我們常見的表達式：如(3+4)*5-6
2. 中綴表達式的求值是我們最熟悉的，但是對于計算機來說并不好操作，因此，在計算結果時，往往會將中綴表達式轉成其它表達式來操作【一般轉成后綴表達式】

三、后綴表達式：

1. 后綴表達式又稱為逆波蘭表達式，與前綴表達式相似，知識運算符位于操作數之后
2. 舉例說明：(3+4)*5-6 對應的后綴表達式就是：3  4 + 5 * 6 -

后綴表達式計算機求值：

從左至右掃描表達式，遇到數字時，將數字壓入棧中，遇到運算符時，彈出棧頂的2個數（棧頂和次頂元素），用運算符將其運算，將其結果壓入到棧中，重復上述過程直到表達式的最右端，最后運算出的值即為表達式的值，例如(3+4)*5-6 對應的后綴表達式就是：3  4 + 5 * 6 -，針對其后綴表達式求值的步驟如下：

1. 從左至右掃描，依次將3、4壓入到棧中
2. 遇到 + 號，彈出4、3，計算3+4=7，將7壓入棧中
3. 將5壓入到棧中
4. 遇到 * 號，彈出5、7，計算5*7=35，將35壓入棧中
5. 將6壓入棧中
6. 最后遇到 - 號，彈出6、35，計算35-6=29，將29壓入棧中即為表達式的最終結果

---

 

案例：完成逆波蘭表達式，要求完成如下任務：

1. 輸入一個逆波蘭表達式，使用棧（Stack）計算其結果
2. 支持小括號和多位數整數，【由于此處講解的是數據結構，因此對計算器進行簡化，只支持對整數的計算】

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//逆波蘭表達式的計算
public class NiPolandExpression {

    public static void main(String[] args) {
        //String expression = "3 4 + 5 * 6 -"; //29
        //String expression = "30 4 + 5 * 6 -"; //164
        //中綴：4 * 5 - 8 + 60 + 8 / 2 ==>后綴：4 5 * 8 - 60 + 8 2 / +
        String expression = "4 5 * 8 - 60 + 8 2 / +"; //76
        //1、將表達式轉成ArrayList集合，后遍歷，每遍歷一個元素將壓棧
        Stack<String> stack = new Stack<>();
        List<String> lists = getList(expression);
        System.out.println(lists);
        for(String ele: lists) {
            if (ele.matches("\\d+")) { //正則表達式：表示匹配一個或者多個整數
                //是數字直接入棧
                stack.push(ele);
            }else {
                //到了這里說明是符號,需要pop出2個操作數
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int ret = 0;
                switch(ele) {
                case "+": 
                    ret = num1 + num2;
                    break;
                case "-":
                    ret = num1 - num2;
                    break;
                case "*":
                    ret = num1 * num2;
                    break;
                case "/":
                    ret = num1 / num2;
                    break;
                    }
                //將計算結果壓入棧中
                stack.push(ret+"");
            }
        }
        int result = Integer.parseInt(stack.pop());
        System.out.println(expression + "最終結果為：" + result);
    }
    
    public static List<String> getList(String expression){
        java.util.List<String> lists = new ArrayList<>();
        String[] arrays = expression.split(" ");
        for(String ele:arrays) {
            lists.add(ele);
        }
        return lists;
     }
    
}