Golang棧結構和字尾表示式實現計算器範例

2022-07-12 14:00:48

引言

只進行基本的四則運算，利用棧結構和字尾表示式來計算數學表示式的值。

本文程式碼：GitHub

執行效果：

問題

如果只能進行兩個值的加減乘除，如何程式設計計算一個數學表示式的值？

比如計算 1+2*3+(4*5+6)*7，我們知道優先順序順序 () 大於 * / 大於 + - ，直接計算得 1+6+26*7 = 189

中綴、字尾表示式的計算

人利用中綴表示式計算值

數學表示式的記法分為字首、中綴和字尾記法，其中中綴就是上邊的算術記法： 1+2*3+(4*5+6)*7，人計算中綴表示式的值：把表示式分為三部分1 2+3 (4*5+6)*7 分別計算值，求和得 189。但這個理解過程在計算機上的實現就複雜了。

計算機利用字尾表示式計算值

中綴表示式 1+2*3+(4*5+6)*7 對應的字尾表示式： 123*+45*6+7*+，計算機使用棧計算字尾表示式值：

計算字尾表示式的程式碼實現

func calculate(postfix string) int {
    stack := stack.ItemStack{}
    fixLen := len(postfix)
    for i := 0; i &lt; fixLen; i++ {
        nextChar := string(postfix[i])
        // 數位：直接壓棧
        if unicode.IsDigit(rune(postfix[i])) {
            stack.Push(nextChar)
        } else {
            // 操作符：取出兩個數位計算值，再將結果壓棧
            num1, _ := strconv.Atoi(stack.Pop())
            num2, _ := strconv.Atoi(stack.Pop())
            switch nextChar {
            case "+":
                stack.Push(strconv.Itoa(num1 + num2))
            case "-":
                stack.Push(strconv.Itoa(num1 - num2))
            case "*":
                stack.Push(strconv.Itoa(num1 * num2))
            case "/":
                stack.Push(strconv.Itoa(num1 / num2))
            }
        }
    }
    result, _ := strconv.Atoi(stack.Top())
    return result
}

現在只需知道如何將中綴轉為字尾，再利用棧計算即可。

中綴表示式轉字尾表示式

轉換過程

從左到右逐個字元遍歷中綴表示式，輸出的字元序列即是字尾表示式：

遇到數位直接輸出

遇到運運算元則判斷：

棧頂運運算元優先順序更低則入棧，更高或相等則直接輸出
棧為空、棧頂是 ( 直接入棧
運運算元是 ) 則將棧頂運運算元全部彈出，直到遇見 )
中綴表示式遍歷完畢，運運算元棧不為空則全部彈出，依次追加到輸出

轉換的程式碼實現

// 中綴表示式轉字尾表示式
func infix2ToPostfix(exp string) string {
    stack := stack.ItemStack{}
    postfix := ""
    expLen := len(exp)
    // 遍歷整個表示式
    for i := 0; i &lt; expLen; i++ {
        char := string(exp[i])
        switch char {
        case " ":
            continue
        case "(":
            // 左括號直接入棧
            stack.Push("(")
        case ")":
            // 右括號則彈出元素直到遇到左括號
            for !stack.IsEmpty() {
                preChar := stack.Top()
                if preChar == "(" {
                    stack.Pop() // 彈出 "("
                    break
                }
                postfix += preChar
                stack.Pop()
            }
            // 數位則直接輸出
        case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
            j := i
            digit := ""
            for ; j &lt; expLen &amp;&amp; unicode.IsDigit(rune(exp[j])); j++ {
                digit += string(exp[j])
            }
            postfix += digit
            i = j - 1 // i 向前跨越一個整數，由於執行了一步多餘的 j++，需要減 1
        default:
            // 操作符：遇到高優先順序的運運算元，不斷彈出，直到遇見更低優先順序運運算元
            for !stack.IsEmpty() {
                top := stack.Top()
                if top == "(" || isLower(top, char) {
                    break
                }
                postfix += top
                stack.Pop()
            }
            // 低優先順序的運運算元入棧
            stack.Push(char)
        }
    }
    // 棧不空則全部輸出
    for !stack.IsEmpty() {
        postfix += stack.Pop()
    }
    return postfix
}
// 比較運運算元棧棧頂 top 和新運運算元 newTop 的優先順序高低
func isLower(top string, newTop string) bool {
    // 注意 a + b + c 的字尾表示式是 ab + c +，不是 abc + +
    switch top {
    case "+", "-":
        if newTop == "*" || newTop == "/" {
            return true
        }
    case "(":
        return true
    }
    return false
}