字首中綴字尾表達式的計算求值

原文在這裡

表達式

字首表達式(波蘭表達式)

1. 字首表達式又稱波蘭式,字首表達式的運算符位于操作數之前
2. 舉例說明： (3+4)×5-6 對應的字首表達式就是 - × + 3 4 5 6

字首表達式求值

字首表達式的計算機求值

從右至左掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素 和 次頂元素），并将結果入棧；重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果

例如:

(3+4)×5-6

對應的字首表達式就是

- × + 3 4 5 6

, 針對字首表達式求值步驟如下:

• 從右至左掃描，将

  6、5、4、3

  壓入堆棧
• 遇到+運算符，是以彈出

  3

  和

  4

  （3為棧頂元素，4為次頂元素），計算出

  3+4

  的值，得

  7

  ，再将7入棧
• 接下來是

  ×

  運算符，是以彈出

  7

  和

  5

  ，計算出

  7×5=35

  ，将

  35

  入棧
• 最後是-運算符，計算出

  35-6

  的值，即

  29

  ，由此得出最終結果

中綴表達式

中綴表達式

中綴表達式就是常見的運算表達式，如

(3+4)×5-6

中綴表達式的求值是我們人最熟悉的，但是對計算機來說卻不好操作(前面我們講的案例就能看的這個問題)，是以，在計算結果時，往往會将中綴表達式轉成其它表達式來操作(一般轉成字尾表達式.)

中綴表達式對于我們人來好搞,計算機他算不算明白,就離譜

計算機不知道怎麼算這個優先級

字尾表達式(逆波蘭表達式)

字尾表達式

字尾表達式又稱逆波蘭表達式,與字首表達式相似，隻是運算符位于操作數之後

中舉例說明： (3+4)×5-6 對應的字尾表達式就是 3 4 + 5 × 6 –

再比如:

正常的表達式	逆波蘭表達式
a+b	a b +
a+(b-c)	a b c - +
a+(b-c)*d	a b c – d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

字尾表達式的計算機求值

從左至右掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 和 棧頂元素），并将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果

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

1. 從左至右掃描，将3和4壓入堆棧；
2. 遇到+運算符，是以彈出4和3（4為棧頂元素，3為次頂元素），計算出3+4的值，得7，再将7入棧；
3. 将5入棧；
4. 接下來是×運算符，是以彈出5和7，計算出7×5=35，将35入棧；
5. 将6入棧；
6. 最後是-運算符，計算出35-6的值，即29，由此得出最終結果

我們完成一個逆波蘭電腦，要求完成如下任務:

1. 輸入一個逆波蘭表達式(字尾表達式)，使用棧(Stack), 計算其結果
2. 支援小括号和多位數整數，因為這裡我們主要講的是資料結構，是以電腦進行簡化，隻支援對整數的計算。
3. 思路分析
4. 代碼完成

package com.atguigu.stack;

/**
 * ClassName:  <br/>
 * Description:  <br/>
 * Date: 2021-02-20 14:27 <br/>
 * @project data_algorithm
 * @package com.atguigu.stack
 */

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

public class PolandNotation {


}
//編寫一個類 Operation 可以傳回一個運算符 對應的優先級
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("不存在該運算符" + operation);
            break;
        }
        return result;
    }

}
//完成對逆波蘭表達式的運算
/*
 * 1)從左至右掃描，将3和4壓入堆棧；
    2)遇到+運算符，是以彈出4和3（4為棧頂元素，3為次頂元素），計算出3+4的值，得7，再将7入棧；
    3)将5入棧；
    4)接下來是×運算符，是以彈出5和7，計算出7×5=35，将35入棧；
    5)将6入棧；
    6)最後是-運算符，計算出35-6的值，即29，由此得出最終結果
 */

public static int calculate(List<String> ls) {
    // 建立給棧, 隻需要一個棧即可
    Stack<String> stack = new Stack<String>();
    // 周遊 ls
    for (String item : ls) {
        // 這裡使用正規表達式來取出數
        if (item.matches("\\d+")) { // 比對的是多位數
            // 入棧
            stack.push(item);
        } else {
            // pop出兩個數，并運算， 再入棧
            int num2 = Integer.parseInt(stack.pop());
            int num1 = Integer.parseInt(stack.pop());
            int res = 0;
            if (item.equals("+")) {
                res = num1 + num2;
            } else if (item.equals("-")) {
                res = num1 - num2;
            } else if (item.equals("*")) {
                res = num1 * num2;
            } else if (item.equals("/")) {
                res = num1 / num2;
            } else {
                throw new RuntimeException("運算符有誤");
            }
            //把res 入棧
            stack.push("" + res);
        }

    }
    //最後留在stack中的資料是運算結果
    return Integer.parseInt(stack.pop());
}
//将一個逆波蘭表達式， 依次将資料和運算符 放入到 ArrayList中
public static List<String> getListString(String suffixExpression) {
    //将 suffixExpression 分割
    String[] split = suffixExpression.split(" ");
    List<String> list = new ArrayList<String>();
    for(String ele: split) {
        list.add(ele);
    }
    return list;

}
//方法：将 中綴表達式轉成對應的List
//  s="1+((2+3)×4)-5";
public static List<String> toInfixExpressionList(String s) {
    //定義一個List,存放中綴表達式 對應的内容
    List<String> ls = new ArrayList<String>();
    int i = 0; //這時是一個指針，用于周遊 中綴表達式字元串
    String str; // 對多位數的拼接
    char c; // 每周遊到一個字元，就放入到c
    do {
        //如果c是一個非數字，我需要加入到ls
        if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
            ls.add("" + c);
            i++; //i需要後移
        } else { //如果是一個數，需要考慮多位數
            str = ""; //先将str 置成"" '0'[48]->'9'[57]
            while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
                str += c;//拼接
                i++;
            }
            ls.add(str);
        }
    }while(i < s.length());
    return ls;//傳回
}
//即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
//方法：将得到的中綴表達式對應的List => 字尾表達式對應的List
public static List<String> parseSuffixExpreesionList(List<String> ls) {
    //定義兩個棧
    Stack<String> s1 = new Stack<String>(); // 符号棧
    //說明：因為s2 這個棧，在整個轉換過程中，沒有pop操作，而且後面我們還需要逆序輸出
    //是以比較麻煩，這裡我們就不用 Stack<String> 直接使用 List<String> s2
    //Stack<String> s2 = new Stack<String>(); // 儲存中間結果的棧s2
    List<String> s2 = new ArrayList<String>(); // 儲存中間結果的Lists2

    //周遊ls
    for(String item: ls) {
        //如果是一個數，加入s2
        if(item.matches("\\d+")) {
            s2.add(item);
        } else if (item.equals("(")) {
            s1.push(item);
        } else if (item.equals(")")) {
            //如果是右括号“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括号為止，此時将這一對括号丢棄
            while(!s1.peek().equals("(")) {
                s2.add(s1.pop());
            }
            s1.pop();//!!! 将 ( 彈出 s1棧， 消除小括号
        } else {
            //當item的優先級小于等于s1棧頂運算符, 将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, 是以按順序輸出就是對應的字尾表達式對應的List

}
           

執行

public static void main(String[] args) {


    //完成将一個中綴表達式轉成字尾表達式的功能
    //說明
    //1. 1+((2+3)×4)-5 => 轉成  1 2 3 + 4 × + 5 –
    //2. 因為直接對str 進行操作，不友善，是以 先将  "1+((2+3)×4)-5" =》 中綴的表達式對應的List
    //   即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    //3. 将得到的中綴表達式對應的List => 字尾表達式對應的List
    //   即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]

    String expression = "1+((2+3)*4)-5";//注意表達式
    List<String> infixExpressionList = toInfixExpressionList(expression);
    System.out.println("中綴表達式對應的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
    System.out.println("字尾表達式對應的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–]

    System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?



    /*

    //先定義給逆波蘭表達式
    //(30+4)×5-6  => 30 4 + 5 × 6 - => 164
    // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
    //測試
    //說明為了友善，逆波蘭表達式 的數字和符号使用空格隔開
    //String suffixExpression = "30 4 + 5 * 6 -";
    String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
    //思路
    //1. 先将 "3 4 + 5 × 6 - " => 放到ArrayList中
    //2. 将 ArrayList 傳遞給一個方法，周遊 ArrayList 配合棧 完成計算

    List<String> list = getListString(suffixExpression);
    System.out.println("rpnList=" + list);
    int res = calculate(list);
    System.out.println("計算的結果是=" + res);

    */
}
           

原文在這裡