表达式解析

之前想写一篇《栈实现的表达式求值》，鸽了。这段时间又在学习编译原理，也有了一些想法，恰好看见Data Structure - Expression Parsing，如获至宝，感觉有点意思。

算术表达式可以使用三种不同但效果等效的的表示法来表示。这些表示法如下：

中缀表示法
前缀表示法（波兰表示法）
后缀表示法（逆波兰表示法）

中缀表示法(Infix Notation)

例如a - b + c，操作符位于操作数之间，这种表示法对人类友好，但对计算机不友好。处理中缀表示法的算法可能难度比较高并且在消耗大量时间和空间。

前缀表示法(Prefix Notation)

这种表示法的操作符位于操作数之前，例如+ a b等同于中缀表示法的a + b。中缀表示法也叫波兰表示法。

后缀表示法(Postfix Notation)

这种表示法也叫逆波兰表示法，操作符在操作数之后，例如a b +等于同中缀表示法的a + b。

以下表格简明地展示了三种表示法的差异。

Sr.No	Infix Notation	Prefix Notation	Postfix Notation
1	a + b	+ a b	a b +
2	(a + b) * c)	* + a b c	a b + c *
3	a * (b + c)	* a + b c	a b c + *
4	a / b + c / d	+ / a b / c d	a b / c d / +
5	(a + b) * (c + d)	* + a b + c d	a b + c d + *
6	((a + b) * c) - d	- * + a b c d	a b + c * d -

解析表达式

专门为中缀表示法设计算法或程序并不是高效的方式。事实上，这些中缀表示法会先转化为后缀或前缀表示法再进行计算。

优先级

当一个操作数位于两个不同的操作符之间时，哪个操作符先获得操作数取决于哪个操作符的优先级比其它操作符高。例如：

a + b * c  ----->  a + (b * c)

由于乘法(*)的优先级高于加法(+)，所以b * c会先计算。

结合性

结合性描述了表达式中存在相同优先级操作符时的规则。例如a + b - 中，+和-拥有相同的优先级，表达式中哪个部分先被计算取决于这些操作符的结合性。这里的+和-都是左结合，所以表达式会以(a + b) - c的形式计算。

优先级和结合性决定了表达式计算的顺序。以下是有关操作符优先级和结合性的表格（从高到低）：

Sr.No.	Operator	Precedence	Associativity
1	乘方(`^`)	最高(Highest)	右结合(Right Associative)
2	乘法(`*`) & 除法(`/`)	第二高(Second Highest)	右结合(Left Associative)
3	加法(`+`) & 减法(`-`)	最低(Lowest)	右结合(Left Associative)

以上表格展示了操作符的默认行为。在表达式计算过程中，计算顺序可以通过小括号来改变。例如a + b * c中，b * c会首先计算，*的优先级比+高。我们可以使用小括号让a + b先计算，(a + b) * c。

后缀算法

Step 1 - scan the expression from left to right(从左到右扫描表达式)
Step 2 - if it is an operand push it to stack(将操作数 push 到 stack)
Step 3 - if it is an operator pull operand from stack and perform operation(遇到操作符，从 stack 中 pull 操作数并执行操作)
Step 4 - store the output of step 3, back to stack(将 Step 3 中的结果 push 回 stack 中)
Step 5 - scan the expression until all operands are consumed(继续扫描表达式直至所有操作数都被消费)
Step 6 - pop the stack and perform operation(将 stack 的数据 pop 出来执行操作)

以下是用 Go 语言改写的的算法实现：

// go version go1.16.7 darwin/amd64
package main

import (
    "fmt"
    "unicode"
)

const size = 25

// char stack
var stack = make([]byte, size)
var top = -1

func push(item byte) {
    top++
    stack[top] = item
}

func pop() byte {
    ret := stack[top]
    top--
    return ret
}

func precedence(symbol byte) int {
    switch symbol {
    case '+', '-':
        return 2
    case '*', '/':
        return 3
    case '^':
        return 4
    case '(', ')', '#':
        return 1
    }

    return 0
}

func isOperator(symbol byte) int {
    switch symbol {
    case '+', '-', '*', '/', '^', '(', ')':
        return 1
    default:
        return 0
    }
}

func convert(infix []byte, postfix *[]byte) {
    var symbol byte = 0
    top++
    stack[top] = '#'

    for i := 0; i < len(infix); i++ {
        symbol = infix[i]

        if isOperator(symbol) == 0 {
            *postfix = append(*postfix, symbol)
        } else {
            if symbol == '(' {
                push(symbol)
            } else {
                if symbol == ')' {
                    for stack[top] != '(' {
                        *postfix = append(*postfix, pop())
                    }

                    pop() // pop put (.
                } else {
                    if precedence(symbol) > precedence(stack[top]) {
                        push(symbol)
                    } else {
                        for precedence(symbol) <= precedence(stack[top]) {
                            *postfix = append(*postfix, pop())
                        }
                        push(symbol)
                    }
                }
            }
        }
    }
    for stack[top] != '#' {
        *postfix = append(*postfix, pop())
    }
}

// int stack
var stackInt = make([]int, size)
var topInt = -1

func pushInt(item int) {
    topInt++
    stackInt[topInt] = item
}

func popInt() int {
    tmp := stackInt[topInt]
    topInt--
    return tmp
}

func evaluate(postfix []byte) int {
    var operand1, operand2 int

    for _, ch := range postfix {
        if unicode.IsDigit(rune(ch)) {
            pushInt(int(ch) - '0')
        } else {
            operand2 = popInt()
            operand1 = popInt()

            switch ch {
            case '+':
                pushInt(operand1 + operand2)
            case '-':
                pushInt(operand1 - operand2)
            case '*':
                pushInt(operand1 * operand2)
            case '/':
                pushInt(operand1 / operand2)
            }
        }
    }

    return stackInt[topInt]
}

func main() {
    infix := []byte("(1+2)*(4+5)")

    var postfix []byte
    convert(infix, &postfix)

    fmt.Printf("Infix expression is: %s(%v)\n", infix, infix)
    fmt.Printf("Postfix expression is: %s(%v)\n", postfix, postfix)
    fmt.Printf("Evaluated expression is: %d\n", evaluate(postfix))
}

William A