關於字尾表示式的java實現過程

2022-07-13 18:02:50

中綴表示法java實現

觀察一個普通的算式：3+4*5

我們當然知道，應該先計算 4*5 再將這個結果和3相加，就能得到最後的結果。

如果是一個複雜一些的算式：3+4*（（5-6）/7+8）

這依然難不倒我們，只要牢記（）的優先順序最高，然後是*/，最後是+-就沒問題了，這就是通常的中綴表示法。

但是通過演演算法分析，這樣的表示式，由於每一次都需要判斷優先順序，所以執行的時間應當是O（N^2）。

在表示式很長很複雜的時候，就需要一種更適合計算機的演演算法來計算了。

字尾表示法

簡介

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表示式方式，在逆波蘭記法中，所有操作符置於運算元的後面，因此也被稱為字尾表示法。

逆波蘭記法不需要括號來標識操作符的優先順序。逆波蘭記法中，操作符置於運算元的後面。

例如表達“三加四”時，寫作“3 4 +”，而不是“3 +4”。如果有多個操作符，操作符置於第二個運算元的後面，所以常規中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5+”：先3減去4，再加上5。——維基百科逆波蘭表示法詞條。

這種表示法有以下特點：

不需要使用括號。和中綴表示式不同，逆波蘭表示式不需要遍歷整個算式來尋找一對括號。
逆波蘭表示式的實現一般基於堆疊。在計算機中，堆疊這種資料結構具有極快的效率。執行時間是O（N）。
不滿足交換律。

逆波蘭表示式的計算方式

例如2*3+4*5

你可以這麼計算，2 和 3 相乘的和是 5，把這個數存起來，再計算 4*5 的值，存起來，最後在計算兩個存在一起的值。寫出來是這樣子的 2 3 * 4 5 * + 。這就是字尾或逆波蘭記法。

採用堆疊實現的過程很簡單，規則如下。

從頭開始讀取。讀取到如果是數位，則將其壓入棧中。如果是一個符號，就取兩次棧頂的元素通過該符號進行計算，再把得到的數壓入棧中。

Java實現

public class PRNCalculator {    
       public static double PRNCal(String PRN){
              Stack<Double> stack = new Stack<Double>();
              String[] ss = PRN.split(" ");
              for(int i = 0; i < ss.length; i++){
                     if(ss[i].matches("\d")) stack.push(Double.valueOf(ss[i]));
                     if(ss[i].matches("[+|-|*|/]")){
                           double b = stack.pop();
                           double a = stack.pop();
                           if(ss[i].equals("+")) stack.push(a + b);
                           if(ss[i].equals("-")) stack.push(a - b);
                           if(ss[i].equals("*")) stack.push(a * b);
                           if(ss[i].equals("/")) stack.push(a / b);
                     }
              }
              return stack.pop();
       }
}

Test類

public class PRNTest {
       public static void main(String[] args) {
              String s = "2 3 * 4 5 * + ";
              double result = PRNCalculator.PRNCal(s);
              System.out.println("輸入的逆波蘭表示式:" + s);
              System.out.println("計算結果:" + result);
       }
}

列印結果：

輸入的逆波蘭表示式:2 3 * 4 5 * +
計算結果:26.0

與中綴記法的轉換

和字尾表示式的計算方法類似，一箇中綴記法轉換到字尾記法，也可以利用堆疊來實現。

從頭開始讀取。如果讀取到的是數位，將其輸出。如果讀取到的是符號，則判斷該符號的優先順序是否高於棧頂或棧為空，是，則壓入棧中；否，則將棧頂輸出並繼續判斷。如果讀取到的是括號，”(“會直接被壓入棧；在讀取到”)”的時候，棧會一直彈出直到遇到”(“。下面是這個轉換的Java實現。

package PRNCalculator;
import java.util.Stack;
public class PRNCalculator {
       public static String PRNTansf(String s){
              Stack<String> stack = new Stack<String>();
              String[] ss = s.split(" ");
              StringBuffer sb = new StringBuffer();
              for(int i = 0; i < ss.length; i++){
                     if(ss[i].matches("\d")) sb.append(ss[i] + " ");
                     if(ss[i].matches("[+|-|*|/|(|)]")) {
                           if(stack.isEmpty()) {
                                  stack.push(ss[i]);
                           } else {
                                  if(ss[i].matches("[+|-]")) {
                                         while(!stack.isEmpty() && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.isEmpty() || stack.peek().matches("[(]")) stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[*|/]")){
                                         while(stack.peek().matches("[*|/]") && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.isEmpty() || stack.peek().matches("[(]") || stack.peek().matches("[+|-]")) stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[(]")) {
                                         stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[)]")){
                                         while(!stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.peek().matches("[(]")) stack.pop();
                                  }
                           }
                     }
              }
              while(!stack.isEmpty()) sb.append(stack.pop()).append(" ");
              return sb.toString();
       }
}

* Test類*

package PRNCalculator;
public class PRNTest {
       public static void main(String[] args) {
              String s = "4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4";
              String PRN = PRNCalculator.PRNTansf(s);
              System.out.println("輸入的表示式為：");
              System.out.println(s);
              System.out.println("輸出的逆波蘭表示式為：");
              System.out.println(PRN);
              double result = PRNCalculator.PRNCal(PRN);
              System.out.println("該表示式計算結果為：");
              System.out.println(result);
       }
}

列印結果：

輸入的表示式為：
4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4
輸出的逆波蘭表示式為：
4 5 + 8 6 8 7 * + * 3 / + 4 +
該表示式計算結果為：
178.33333333333334

java字尾表示式的計算

實現方法

從左至右掃描表示式

遇到數位時，將數位壓棧，遇到運運算元時，彈出棧頂的兩個數，計算並將結果入棧

重複2直到表示式最右端，最後運算得出的值即為表示式的結果

範例

計算字尾表示式的值：1 2 3 + 4 × + 5 -

從左至右掃描，將1，2，3壓入棧；

遇到+運運算元，3和2彈出，計算2+3的值，得到5，將5壓入棧；

遇到4，將4壓入棧

遇到×運運算元，彈出4和5，計算5×4的值，得到20，將20壓入棧；

遇到+運運算元，彈出20和1，計算1+20的值，得到21，將21壓入棧；

遇到5，將5壓入棧；

遇到-運運算元，彈出5和21，計算21-5的值，得到16為最終結果

程式碼實現

public class ReversePolishNotation {

    public static void main(String[] args) {
        String notation = "10 2 3 + 4 * + 5 -";
        ReversePolishNotation reversePN = new ReversePolishNotation();
        Stack<Integer> numStack = new Stack<>();
        //以空格分隔上述表示式，存到陣列中
        String[] s = notation.split(" ");
        //遍歷陣列
        for (int i = 0; i < s.length; i++) {
            if (!reversePN.isOperator(s[i])){
                //如果不是運運算元，則壓棧
                numStack.push(Integer.parseInt(s[i]));
            } else {
                //為運運算元，則取出棧頂的兩個數位進行運算
                int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]);
                //將結果壓棧
                numStack.push(result);
            }
        }
        //迴圈結束，棧中僅剩的一個元素及為結果
        System.out.println(numStack.pop());
    }
    //判斷是否是運運算元
    public boolean isOperator(String oper){
        return oper.equals("+") ||oper.equals("-")  ||oper.equals("*")  ||oper.equals("/") ;
    }
    //計算
    public int calculation(int num1, int num2, String oper){
        switch (oper){
            case "+":
                return num2 + num1;
            case "-":
                return num2 - num1;
            case "*":
                return num2 * num1;
            case "/":
                return num2 / num1;
            default:
                return 0;
        }
    }
}

以上為個人經驗，希望能給大家一個參考，也希望大家多多支援it145.com。