利用棧解析算術(shù)表達(dá)式

在編寫編譯器時(shí)經(jīng)常需要實(shí)現(xiàn)對(duì)算術(shù)表達(dá)式的解析，然而對(duì)于計(jì)算機(jī)的算法來說如果直接求解算術(shù)表達(dá)式的值，還是相當(dāng)困難的。因此解析算術(shù)表達(dá)式經(jīng)常分步實(shí)現(xiàn)：

1.將中綴的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
2.計(jì)算后綴表達(dá)式的值

在正式介紹算法的實(shí)現(xiàn)之前，先介紹一點(diǎn)有關(guān)表達(dá)式的基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

1. 后綴表達(dá)式

日常算術(shù)表達(dá)式是將操作符(operator)(+,-,*,/)放在兩個(gè)操作數(shù)(operands)(數(shù)字，或者代表數(shù)字的字母)中間的，由于操作符寫在操作數(shù)中間，所以把這種寫法稱為中綴表達(dá)式.對(duì)人類而言，中綴表達(dá)式便于理解和閱讀.

后綴表達(dá)式，又稱為波蘭逆序表達(dá)式(Reverse Polish Notation)，它是將操作符放在操作數(shù)后面的一種表達(dá)式的記錄方法，比如A+B變成AB+，這是一種便于計(jì)算機(jī)計(jì)算的表達(dá)式.

中綴表達(dá)式 后綴表達(dá)式
A+B-C AB+C-
A*B/C AB*C/
A+B*C ABC*+
A+B*(C-D/(E+F)) ABCDEF+/-*+

2. 棧

棧(Stack)是計(jì)算機(jī)中應(yīng)用的非常多的一種數(shù)據(jù)結(jié)構(gòu)，其遵循先進(jìn)后出的規(guī)律，可以用數(shù)組或者鏈表來實(shí)現(xiàn)棧，本文中就是使用數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧.

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式是解析算術(shù)表達(dá)式中最重要的一步，本文中通過觀察幾個(gè)示例然后總結(jié)出轉(zhuǎn)換規(guī)律.

1. 分析

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的規(guī)則和計(jì)算中綴表達(dá)式值的規(guī)則相似，不需要做計(jì)算，只是把操作數(shù)和操作符重新排列為另一種形式：后綴表示法.

從左到右的掃描中綴表達(dá)式，遇到操作數(shù)直接輸出，遇到操作符則按照轉(zhuǎn)換規(guī)則入?；蛘咻敵?以將A*(B+C)的轉(zhuǎn)換為例：

讀取的字符 分解中綴表達(dá)式 求后綴表達(dá)式 棧中內(nèi)容
A A A
+ A+ B +
B A+B AB +
* A+B* AB +*
( A+B*( AB +*(
C A+B*(C ABC +*(
- A+B*(C- ABC +*(-
D A+B*(C-D ABCD +*(-
) A+B*(C-D) ABCD- +*(
A+B*(C-D) ABCD- +*(
A+B*(C-D) ABCD- +*
A+B*(C-D ABCD-* +
A+B*(C-D) ABCD-*+

從中可以看出，操作符的初始順序在中綴表達(dá)式中是+*-，但是在后綴表達(dá)式中變成了-*+，這是因?yàn)?code>*比+的優(yōu)先級(jí)別高，而-在括號(hào)中所以優(yōu)先級(jí)比*高.

2. 規(guī)律總結(jié)

通過觀察上面的轉(zhuǎn)換例子，可以一般地總結(jié)出中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的轉(zhuǎn)換規(guī)則.

| 從輸入中讀取的字符 | 動(dòng)作 |
| :----------------: | |
|操作數(shù) | 寫至輸出(postfix)|
|左括號(hào) ( | 入棧 |
|右括號(hào) ) | 棧非空時(shí)，重復(fù)以下步驟：彈出一項(xiàng)，若項(xiàng)不為（，則寫至輸出，項(xiàng)為(，則退出循環(huán)|
|Operator(opThis)| 若棧空， 推opThis；否則，棧非空時(shí)，重復(fù)：彈出一項(xiàng)，若項(xiàng)為（，推其入棧；或項(xiàng)為operator(opTop)，且，若opTop<opThis，推入opTop，或opTop>=opThis，輸出opTop，若opTop<opThis，則退出循環(huán)，或項(xiàng)為(，推入opThis|
|沒有更多項(xiàng) |當(dāng)棧非空時(shí)，彈出項(xiàng)目，將其輸出|

3. 代碼實(shí)現(xiàn)

利用java實(shí)現(xiàn)以上轉(zhuǎn)換過程，關(guān)鍵如下：

/**
 * 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
 *
 * @return 轉(zhuǎn)換結(jié)果
 */
public String doTrans() {
    for (int j = 0; j < input.length(); j++) {
        char ch = input.charAt(j);
        theStack.displayStack("For " + ch + " ");
        switch (ch) {
            case '+':
            case '-':
                gotOper(ch, 1);
                break;
            case '*':
            case '/':
                gotOper(ch, 2);
                break;
            case '(':
                theStack.push(ch);
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                output += ch;
                break;
        }
    }
    while (!theStack.isEmpty()) {
        theStack.displayStack("While ");
        output += theStack.pop();
    }
    theStack.displayStack("End ");
    return output;
}

public void gotOper(char onThis, int prec1) {
    while (!theStack.isEmpty()) {
        char onTop = theStack.pop();
        if (onTop == '(') {
            theStack.push(onTop);
            break;
        } else {
            int prec2;
            if (onTop == '+' || onTop == '-') {
                prec2 = 1;
            } else {
                prec2 = 2;
            }

            if (prec2 < prec1) {
                theStack.push(onTop);
                break;
            } else {
                output += onTop;
            }
        }
    }
    theStack.push(onThis);
}

public void gotParen(char ch) {
    while (!theStack.isEmpty()) {
        char chx = theStack.pop();
        if (chx == '(') {
            break;
        } else {
            output += chx;
        }
    }
}

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

相對(duì)于轉(zhuǎn)換而言，計(jì)算后綴表達(dá)式是比較容易的.從左到右掃描輸入(后綴表達(dá)式)，碰到操作數(shù)將之入棧，每碰到一個(gè)操作符，從棧中提出兩個(gè)操作數(shù)，用操作符將其執(zhí)行運(yùn)算，將計(jì)算結(jié)果入棧.

1. 代碼實(shí)現(xiàn)

/**
 * 對(duì)后綴表達(dá)式求值
 *
 * @return 求值結(jié)果
 */
public int doParse() {
    int num1, num2, interAns = 0;
    char ch;
    theStack = new StackY(20);
    for (int j = 0; j < input.length(); j++) {
        ch = input.charAt(j);
        theStack.displayStack("" + ch + " ");
        if (ch >= '0' && ch <= '9') {
            theStack.push((ch - '0'));
        } else {
            num2 = theStack.pop();
            num1 = theStack.pop();
            switch (ch) {
                case '+':
                    interAns = num1 + num2;
                    break;
                case '-':
                    interAns = num1 - num2;
                    break;
                case '*':
                    interAns = num1 * num2;
                    break;
                case '/':
                    interAns = num1 / num2;
                    break;
                default:
                    interAns = 0;
            }
            theStack.push(interAns);
        }

    }
    interAns = theStack.pop();
    return interAns;
}

括號(hào)匹配

在用戶輸入表達(dá)式的過程中，有時(shí)會(huì)出現(xiàn)左右括號(hào)不匹配的情況，對(duì)于這種情況，一個(gè)優(yōu)秀的算術(shù)解析器應(yīng)該能夠識(shí)別出來并報(bào)錯(cuò).這個(gè)實(shí)際上就是括號(hào)匹配的問題，也是利用棧來解決的，實(shí)現(xiàn)思路如下.

算法從左到右不斷掃描輸入的字符串，如果為左分隔符((、[、{)，直接入棧；如果為右分隔符，彈出棧頂?shù)淖蠓指舴?，并且查看它是否和右分隔符匹配。如果它們不匹配則報(bào)錯(cuò).如果棧中沒有左分隔符和右分隔符匹配，或者一直存在著沒有被匹配的分隔符(棧非空)，程序也報(bào)錯(cuò).

1. 代碼實(shí)現(xiàn)

public boolean check() {
    int size = input.length();
    StackY<Character> theStack = new StackY<>(size);
    char ch, chx;
    for (int j = 0; j < size; j++) {
        ch = input.charAt(j);
        switch (ch) {
            case '(':
                theStack.push(ch);
                break;
            case ')':
                if (!theStack.isEmpty()) {
                    chx = theStack.pop();
                    if (chx != '(') return false;
                } else
                    return false;
            default:
                break;
        }
    }
    if (!theStack.isEmpty())
        return false;
    return true;
}

附錄

1. 說明

  • 為了實(shí)現(xiàn)方便，本算法只針對(duì)一位數(shù)的計(jì)算有效，即12*2不能解析，3*9可以解析
  • 參考資料：Java數(shù)據(jù)結(jié)構(gòu)和算法(第二版)

2. 完整代碼

package com.lxl.stack;

import jdk.internal.org.objectweb.asm.signature.SignatureWriter;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 利用棧解析算術(shù)表達(dá)式
 *
 * @author lixiaolin
 * @createDate 2016-05-31 16:59
 */
public class InfixApp {
    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        return br.readLine();
    }

    public static void main(String[] args) throws IOException {
        String input, output;
        int result;
        while (true) {
            System.out.println("Enter infix: ");
            System.out.flush();
            input = getString();
            if (input == "") {
                break;
            }
            Bracket bracket =new Bracket(input);
            if (!bracket.check()){
                System.out.println("The input is invalid...");
                break;
            }
            InToPost theTrans = new InToPost(input);
            output = theTrans.doTrans();
            System.out.println("Postfix is " + output);
            ParsePost parsePost = new ParsePost(output);
            result = parsePost.doParse();
            System.out.println("Final result is : " + result);
        }
    }
}

/**
 * 輔助棧
 *
 * @param <T>
 */
class StackY<T> {
    private int maxSize;
    private int top;
    private Object[] stackArray;

    public StackY(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1;
        stackArray = new Object[maxSize];
    }

    public void push(T value) {
        stackArray[++top] = value;
    }

    public T peek() {
        return (T) stackArray[top];
    }

    public T pop() {
        return (T) stackArray[top--];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public T peekN(int n) {
        return (T) stackArray[n];
    }

    public void displayStack(String s) {
        System.out.print(s);
        System.out.print("Stack (botton->top): ");
        for (int i = 0; i < size(); i++) {
            System.out.print(peekN(i));
            System.out.print(" ");
        }
        System.out.println("");
    }
}

class InToPost {
    private String input;
    private StackY<Character> theStack;
    private String output = "";

    public InToPost(String input) {
        this.input = input;
        theStack = new StackY(input.length());
    }

    /**
     * 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
     *
     * @return 轉(zhuǎn)換結(jié)果
     */
    public String doTrans() {
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            theStack.displayStack("For " + ch + " ");
            switch (ch) {
                case '+':
                case '-':
                    gotOper(ch, 1);
                    break;
                case '*':
                case '/':
                    gotOper(ch, 2);
                    break;
                case '(':
                    theStack.push(ch);
                    break;
                case ')':
                    gotParen(ch);
                    break;
                default:
                    output += ch;
                    break;
            }
        }
        while (!theStack.isEmpty()) {
            theStack.displayStack("While ");
            output += theStack.pop();
        }
        theStack.displayStack("End ");
        return output;
    }

    public void gotOper(char onThis, int prec1) {
        while (!theStack.isEmpty()) {
            char onTop = theStack.pop();
            if (onTop == '(') {
                theStack.push(onTop);
                break;
            } else {
                int prec2;
                if (onTop == '+' || onTop == '-') {
                    prec2 = 1;
                } else {
                    prec2 = 2;
                }

                if (prec2 < prec1) {
                    theStack.push(onTop);
                    break;
                } else {
                    output += onTop;
                }
            }
        }
        theStack.push(onThis);
    }

    public void gotParen(char ch) {
        while (!theStack.isEmpty()) {
            char chx = theStack.pop();
            if (chx == '(') {
                break;
            } else {
                output += chx;
            }
        }
    }
}

class ParsePost {
    private String input;
    private StackY<Integer> theStack;

    public ParsePost(String input) {
        this.input = input;
    }

    /**
     * 對(duì)后綴表達(dá)式求值
     *
     * @return 求值結(jié)果
     */
    public int doParse() {
        int num1, num2, interAns = 0;
        char ch;
        theStack = new StackY(20);
        for (int j = 0; j < input.length(); j++) {
            ch = input.charAt(j);
            theStack.displayStack("" + ch + " ");
            if (ch >= '0' && ch <= '9') {
                theStack.push((ch - '0'));
            } else {
                num2 = theStack.pop();
                num1 = theStack.pop();
                switch (ch) {
                    case '+':
                        interAns = num1 + num2;
                        break;
                    case '-':
                        interAns = num1 - num2;
                        break;
                    case '*':
                        interAns = num1 * num2;
                        break;
                    case '/':
                        interAns = num1 / num2;
                        break;
                    default:
                        interAns = 0;
                }
                theStack.push(interAns);
            }

        }
        interAns = theStack.pop();
        return interAns;
    }
}

class Bracket {
    private String input;

    public Bracket(String input) {
        this.input = input;
    }

    public boolean check() {
        int size = input.length();
        StackY<Character> theStack = new StackY<>(size);
        char ch, chx;
        for (int j = 0; j < size; j++) {
            ch = input.charAt(j);
            switch (ch) {
                case '(':
                    theStack.push(ch);
                    break;
                case ')':
                    if (!theStack.isEmpty()) {
                        chx = theStack.pop();
                        if (chx != '(') return false;
                    } else
                        return false;
                default:
                    break;
            }
        }
        if (!theStack.isEmpty())
            return false;
        return true;
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容