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

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

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

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

觀察一個(gè)普通的算式：3+4*5

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

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

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

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

在表達(dá)式很長(zhǎng)很復(fù)雜的時(shí)候，就需要一種更適合計(jì)算機(jī)的算法來(lái)計(jì)算了。

后綴表示法

簡(jiǎn)介

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

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

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

這種表示法有以下特點(diǎn)：

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

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

例如2*3+4*5

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

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

從頭開(kāi)始讀取。讀取到如果是數(shù)字，則將其壓入棧中。如果是一個(gè)符號(hào)，就取兩次棧頂?shù)脑赝ㄟ^(guò)該符號(hào)進(jìn)行計(jì)算，再把得到的數(shù)壓入棧中。

Java實(shí)現(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("計(jì)算結(jié)果:" + result);
? ? ? ?}
}

打印結(jié)果：

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

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

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

從頭開(kāi)始讀取。如果讀取到的是數(shù)字，將其輸出。如果讀取到的是符號(hào)，則判斷該符號(hào)的優(yōu)先級(jí)是否高于棧頂或棧為空，是，則壓入棧中；否，則將棧頂輸出并繼續(xù)判斷。如果讀取到的是括號(hào)，”(“會(huì)直接被壓入棧；在讀取到”)”的時(shí)候，棧會(huì)一直彈出直到遇到”(“。下面是這個(gè)轉(zhuǎn)換的Java實(shí)現(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á)式計(jì)算結(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á)式計(jì)算結(jié)果為：
178.33333333333334

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

實(shí)現(xiàn)方法

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

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

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

示例

計(jì)算后綴表達(dá)式的值：1 2 3 + 4 × + 5 -

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

遇到+運(yùn)算符，3和2彈出，計(jì)算2+3的值，得到5，將5壓入棧；

遇到4，將4壓入棧

遇到×運(yùn)算符，彈出4和5，計(jì)算5×4的值，得到20，將20壓入棧；

遇到+運(yùn)算符，彈出20和1，計(jì)算1+20的值，得到21，將21壓入棧；

遇到5，將5壓入棧；

遇到-運(yùn)算符，彈出5和21，計(jì)算21-5的值，得到16為最終結(jié)果

代碼實(shí)現(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])){
                //如果不是運(yùn)算符，則壓棧
                numStack.push(Integer.parseInt(s[i]));
            } else {
                //為運(yùn)算符，則取出棧頂?shù)膬蓚€(gè)數(shù)字進(jìn)行運(yùn)算
                int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]);
                //將結(jié)果壓棧
                numStack.push(result);
            }
        }
        //循環(huán)結(jié)束，棧中僅剩的一個(gè)元素及為結(jié)果
        System.out.println(numStack.pop());
    }
    //判斷是否是運(yùn)算符
    public boolean isOperator(String oper){
        return oper.equals("+") ||oper.equals("-")  ||oper.equals("*")  ||oper.equals("/") ;
    }
    //計(jì)算
    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;
        }
    }
}

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

您可能感興趣的文章: