關(guān)于后綴表達(dá)式的java實現(xiàn)過程

更新時間：2022年07月13日 15:28:27 作者：fuyun_0803

這篇文章主要介紹了關(guān)于后綴表達(dá)式的java實現(xiàn)過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

中綴表示法java實現(xiàn)

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

我們當(dāng)然知道，應(yīng)該先計算 4*5 再將這個結(jié)果和3相加，就能得到最后的結(jié)果。

如果是一個復(fù)雜一些的算式：3+4*（（5-6）/7+8）

這依然難不倒我們，只要牢記（）的優(yōu)先級最高，然后是*/，最后是+-就沒問題了，這就是通常的中綴表示法。

但是通過算法分析，這樣的表達(dá)式，由于每一次都需要判斷優(yōu)先級，所以運行的時間應(yīng)當(dāng)是O（N^2）。

在表達(dá)式很長很復(fù)雜的時候，就需要一種更適合計算機的算法來計算了。

后綴表示法

簡介

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數(shù)學(xué)家揚·武卡謝維奇1920年引入的數(shù)學(xué)表達(dá)式方式，在逆波蘭記法中，所有操作符置于操作數(shù)的后面，因此也被稱為后綴表示法。

逆波蘭記法不需要括號來標(biāo)識操作符的優(yōu)先級。逆波蘭記法中，操作符置于操作數(shù)的后面。

例如表達(dá)“三加四”時，寫作“3 4 +”，而不是“3 +4”。如果有多個操作符，操作符置于第二個操作數(shù)的后面，所以常規(guī)中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5+”：先3減去4，再加上5。——維基百科逆波蘭表示法詞條。

這種表示法有以下特點：

不需要使用括號。和中綴表達(dá)式不同，逆波蘭表達(dá)式不需要遍歷整個算式來尋找一對括號。
逆波蘭表達(dá)式的實現(xiàn)一般基于堆棧。在計算機中，堆棧這種數(shù)據(jù)結(jié)構(gòu)具有極快的效率。運行時間是O（N）。
不滿足交換律。

逆波蘭表達(dá)式的計算方式

例如2*3+4*5

你可以這么計算，2 和 3 相乘的和是 5，把這個數(shù)存起來，再計算 4*5 的值，存起來，最后在計算兩個存在一起的值。寫出來是這樣子的 2 3 * 4 5 * + 。這就是后綴或逆波蘭記法。

采用堆棧實現(xiàn)的過程很簡單，規(guī)則如下。

從頭開始讀取。讀取到如果是數(shù)字，則將其壓入棧中。如果是一個符號，就取兩次棧頂?shù)脑赝ㄟ^該符號進行計算，再把得到的數(shù)壓入棧中。

Java實現(xiàn)

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("輸入的逆波蘭表達(dá)式:" + s);
? ? ? ? ? ? ? System.out.println("計算結(jié)果:" + result);
? ? ? ?}
}

打印結(jié)果：

輸入的逆波蘭表達(dá)式:2 3 * 4 5 * +
計算結(jié)果:26.0

與中綴記法的轉(zhuǎn)換

和后綴表達(dá)式的計算方法類似，一個中綴記法轉(zhuǎn)換到后綴記法，也可以利用堆棧來實現(xiàn)。

從頭開始讀取。如果讀取到的是數(shù)字，將其輸出。如果讀取到的是符號，則判斷該符號的優(yōu)先級是否高于棧頂或棧為空，是，則壓入棧中；否，則將棧頂輸出并繼續(xù)判斷。如果讀取到的是括號，”(“會直接被壓入棧；在讀取到”)”的時候，棧會一直彈出直到遇到”(“。下面是這個轉(zhuǎn)換的Java實現(xiàn)。

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("輸入的表達(dá)式為：");
? ? ? ? ? ? ? System.out.println(s);
? ? ? ? ? ? ? System.out.println("輸出的逆波蘭表達(dá)式為：");
? ? ? ? ? ? ? System.out.println(PRN);
? ? ? ? ? ? ? double result = PRNCalculator.PRNCal(PRN);
? ? ? ? ? ? ? System.out.println("該表達(dá)式計算結(jié)果為：");
? ? ? ? ? ? ? System.out.println(result);
? ? ? ?}
}

打印結(jié)果：

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

java后綴表達(dá)式的計算

實現(xiàn)方法

從左至右掃描表達(dá)式

遇到數(shù)字時，將數(shù)字壓棧，遇到運算符時，彈出棧頂?shù)膬蓚€數(shù)，計算并將結(jié)果入棧

重復(fù)2直到表達(dá)式最右端，最后運算得出的值即為表達(dá)式的結(jié)果

示例

計算后綴表達(dá)式的值：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為最終結(jié)果

代碼實現(xiàn)

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<>();
        //以空格分隔上述表達(dá)式，存到數(shù)組中
        String[] s = notation.split(" ");
        //遍歷數(shù)組
        for (int i = 0; i < s.length; i++) {
            if (!reversePN.isOperator(s[i])){
                //如果不是運算符，則壓棧
                numStack.push(Integer.parseInt(s[i]));
            } else {
                //為運算符，則取出棧頂?shù)膬蓚€數(shù)字進行運算
                int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]);
                //將結(jié)果壓棧
                numStack.push(result);
            }
        }
        //循環(huán)結(jié)束，棧中僅剩的一個元素及為結(jié)果
        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;
        }
    }
}

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: