[[387421]]

 前綴表達式(波蘭表達式)

前綴表達式又稱波蘭表達式,前綴表達式的運算符位于操作符之前,如(3+4)*5-6對應的前綴表達式就是- * + 3 4 5 6

前綴表達式的計算機求值

從右至左掃描表達式,遇到數字時,就壓入堆棧,遇到運算符時,彈出棧頂的兩個數,用運算符對他們做相應的計算(棧頂元素和次頂元素),并將結果入棧;重復上述過程直到表達式最左端,最后運算得出的值即為表達式的結果.

例如:(3+4)*5-6對應的前綴表達式就是- * + 3 4 5 6,針對前綴表達式求值步驟如下:

1. 從右至左掃描,將6,5,4,3壓入堆棧.
2. 遇到+運算符,因此彈出3和4(3為棧頂元素,4為次頂元素),計算出3+4的值,得7,再將7入棧.
3. 接下來是*運算符,因此彈出7和5,計算出35,將35入棧.
4. 最后是-運算符,計算出35-6的值,即29,由此得出最終結果.

中綴表達式

中綴表達式就是常見的運算表達式,如(3*4)+5-6.中綴表達式的求值是我們人最熟悉的,但是對計算機來說卻不好操作,因此在計算結果時,往往會將中綴表達式轉換成其他表達式來操作(一般轉換成后綴表達式).

后綴表達式

后綴表達式又稱為逆波蘭表達式,與前綴表達式類似,只是運算符在操作數之后.

如(3+4)*5-6對應的后綴表達式就是3 4 + 5 * 6 -

再比如

后綴表達式的計算機求值

從左至右掃描表達式,遇到數字時,將數字壓入堆棧,遇到運算符時,彈出棧頂的兩個元素,用運算符對它們做對應的計算(棧頂元素和次頂元素),并將結果入棧,重復上述過程直到表示最右端,最后運算得出的值即為表達式的結果.

例如:(3+4)*5-6對應的后綴表達就是 3 4 + 5 * 6 -,針對后綴表達式求值步驟如下:

1. 從左至右掃描,將3和4壓入堆棧.
2. 遇到+運算符,因此彈出4和3(4為棧頂元素,3為次頂元素),計算出7,再將7入棧.
3. 將5入棧.
4. 遇到*運算符,因此單出5和7,計算出35,將35入棧.
5. 將6入棧.
6. 最后是-運算符,計算出29,由此得出最終結果.

中綴表達式轉后綴表達式

1.初始化兩個棧:運算符棧s1和存儲空中間結果的棧s2.

2.從左至右掃描表達式.

3.遇到操作數時,將其壓入s2.

4.遇到運算符時,比較其與s1棧頂運算符的優先級.

1. 如果s1為空,或者棧頂運算符為左括號"(",則直接將此運算符入棧.
2. 否則,若優先級比棧頂運算符的高,也將運算符壓入s1.
3. 否則,將s1棧頂的運算符彈出并壓入s2中,再次轉到(4.1)與s1中新的棧頂運算符相比較.

5.遇到括號時:

1. 如果是左括號"(",則直接壓入s1.
2. 如果是右括號")",則依次彈出s1棧頂的運算符,并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄.

6.重復步驟2至5,直到表達式最右邊.

7.將s1中剩余的運算符依次彈出并壓入s2.

8.依次彈出s2中的元素并輸出,結果的逆序即為中綴表達式對應的后綴表達式.

簡單的后綴表達式計算器

package com.structures.stack; 
 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import java.util.Stack; 
 
public class PolandNotation { 
    public static void main(String[] args) { 
        //先給出逆波蘭表達式(3+4)*5-6==>3 4 + 5 * 6 - 
        String expression = "1+(((2+3)*4))-5"; 
        List<String> toInfixExpressionList = toInfixExpressionList(expression); 
        System.out.println(toInfixExpressionList); 
        List<String> suffixExpressList = parseSuffixExpressList(toInfixExpressionList); 
        System.out.println(suffixExpressList); 
        System.out.println(calculate(suffixExpressList)); 
        /* 
        [1, +, (, (, (, 2, +, 3, ), *, 4, ), ), -, 5] 
        不存在該運算符 
        不存在該運算符 
        [1, 2, 3, +, 4, *, +, 5, -] 
        16 
        */ 
    } 
 
    //將中綴表達式對應的List轉換成后綴表達式對應的List 
    public static List<String> parseSuffixExpressList(List<String> ls) { 
        //定義兩個棧 
        Stack<String> s1 = new Stack<>();//符號棧 
 
        //說明:因為s2這個棧,在整個轉換過程中,沒有pop操作,而且后面還要逆序操作. 
        //因此比較麻煩,這里我們就不用Stack<String> 直接使用List<String> s2. 
        //Stack<String> s2 = new Stack<>();//存儲中間結果的棧s2 
        List<String> s2 = new ArrayList<>(); 
        for (String item : ls) { 
            if (item.matches("\\d+")) { 
                s2.add(item); 
            } else if (item.equals("(")) { 
                s1.push("("); 
            } else if (item.equals(")")) { 
                //如果是右括號")",則依次彈出s1棧頂的運算符,并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄. 
                while (!s1.peek().equals("(")) { 
                    s2.add(s1.pop()); 
                } 
                s1.pop(); 
            } else { 
                //當item優先級小于等于棧頂運算符,將s1棧頂的運算符彈出并壓入s2中,再次轉到(4.1)與s1中新的棧頂運算符相比較. 
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { 
                    s2.add(s1.pop()); 
                } 
                //還需要將item壓入棧 
                s1.push(item); 
            } 
        } 
        //將s1中剩余的運算符依次彈出并壓入s2 
        while (s1.size() != 0) { 
            s2.add(s1.pop()); 
        } 
        return s2; 
    } 
 
    //將中綴表達式轉List 
    public static List<String> toInfixExpressionList(String s) { 
        List<String> ls = new ArrayList<>(); 
 
        int i = 0; 
        String str;//對多位數拼接 
        char c; 
        do { 
            //如果c是一個非數字,直接加入ls 
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57) { 
                ls.add("" + c); 
                i++; 
            } else { 
                //如果是一個數,需要考慮多位數問題. 
                str = ""; 
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { 
                    str += c; 
                    i++; 
                } 
            } 
        } while (i < s.length()); 
        return ls; 
    } 
 
    //根據逆波蘭表達式求值 
    public static int calculate(List<String> ls) { 
        Stack<String> stack = new Stack<>(); 
        for (String item : ls) { 
            //這里使用正則表達式來取出數,匹配的是多位數 
            if (item.matches("\\d+")) { 
                stack.push(item); 
            } else { 
                int num2 = Integer.parseInt(stack.pop()); 
                int num1 = Integer.parseInt(stack.pop()); 
                int res = 0; 
                switch (item) { 
                    case "+": 
                        res = num1 + num2; 
                        break; 
                    case "-": 
                        res = num1 - num2; 
                        break; 
                    case "*": 
                        res = num1 * num2; 
                        break; 
                    case "/": 
                        res = num1 / num2; 
                        break; 
                    default: 
                        throw new RuntimeException("運算符有誤"); 
                } 
                stack.push(res + ""); 
            } 
        } 
        return Integer.parseInt(stack.pop()); 
    } 
} 
 
//根據運算符返回對應的優先級數字 
class Operation { 
    private static int ADD = 1; 
    private static int SUB = 1; 
    private static int MUL = 2; 
    private static int DIV = 2; 
 
    public static int getValue(String operation) { 
        int result = 0; 
        switch (operation) { 
            case "+": 
                result = ADD; 
                break; 
            case "-": 
                result = SUB; 
                break; 
            case "*": 
                result = MUL; 
                break; 
            case "/": 
                result = DIV; 
                break; 
            default: 
                System.out.println("不存在該運算符"); 
                break; 
        } 
        return result; 
    } 
} 

 【編輯推薦】