算法：中缀表达式转后缀表达式

调度场算法

中缀表达式转后缀表达式又称调度场算法。

可参考 维基百科：调度场算法

算法步骤

0. 从左到右扫描中缀表达式
1. 遇到操作数直接入栈s2
2. 遇到运算符时，比较运算符栈s1的栈顶运算符的优先级 2.1 若s1为空，或栈顶运算符为左括号(则直接入s1 2.2 若遇到的运算符比s1栈顶的运算符优先级高，则直接入s1 2.3 若遇到的运算符比s1栈顶的运算符优先级小或等于，则先弹出s1栈顶的运算符压入到s2中，再跳转至2.1与s1新的栈顶运算符进行比较
3. 遇到括号时 3.1 若遇到的是左括号(则直接入s2栈 3.2 若遇到的是右括号)则依次弹出s1中的运算符并压入s2，直到遇到右括号为止，并将一对括号丢弃
4. 将s1剩余栈压入s2
5. s2中pop出的元素的逆序即中缀表达式转后缀表达式的结果

辅助方法

IsOperator：判断是否是运算符。

CalcValue：两数运算。

CalcPriority：操作数计算运算优先级。

func IsOperator(char string) bool {
    return char == "+" || char == "-" || char == "*" || char == "/" || char == "(" || char == ")"
}

func CalcValue(num1, num2 float32, operator string) float32 {
    if operator == "*" {
        return num1 * num2
    } else if operator == "/" {
        return num1 / num2
    } else if operator == "+" {
        return num1 + num2
    } else if operator == "-" {
        return num1 - num2
    } else {
        return -1
    }
}

func CalcPriority(operator string) int {
    if operator == "*" || operator == "/" {
        return 1000
    } else if operator == "+" || operator == "-" {
        return 100
    } else {
        return 0
    }
}

实现

后缀表达式的计算方式：从左往右扫描后缀表达式，遇到数字放入数字栈，遇到运算符则弹出数字栈中的两个元素，栈顶的元素作为后一个元素，次顶元素作为前一个元素，如：A-B减法运算中A是次顶元素，B是栈顶元素，将运算完成得到的数再次入数字栈，步骤循环，最后在数字栈中只剩最后一个元素即是后缀表达式的最终结果。

func main() {
    infixNotationExpression := "1+((2+3)*4)-5"
    arr1 := strings.Split(infixNotationExpression, "")
    finalStr := ""
    stack := &Stack{-1, make([]interface{}, 10)}
    for _, str := range arr1 {
        if IsOperator(str) {
            if str == "(" {
                // 入运算符栈
                stack.Put(str)
            } else if str == ")" {
                // pop 到 ( 为止
                for stack.Peek().(string) != "(" {
                    finalStr += stack.Pop().(string) + " "
                }
                stack.Pop()
            } else {
                for {
                    empty := stack.IsEmpty()
                    if !empty && (CalcPriority(str) <= CalcPriority(stack.Peek().(string))) {
                        finalStr += stack.Pop().(string) + " "
                    } else {
                        // 入运算符栈
                        stack.Put(str)
                        break
                    }
                }
            }
        } else {
            finalStr += str + " "
        }
    }

    // 将运算符中的元素都弹出压入s2
    for !stack.IsEmpty() {
        finalStr += stack.Pop().(string) + " "
    }

    finalStr = strings.TrimRight(finalStr," ")
    fmt.Println("finalStr#", finalStr)

    //expression := "3 4 + 5 * 6 -"
    arr := strings.Split(finalStr, " ")
    numStack := &Stack{-1, make([]interface{}, 10)}
    for _, value := range arr {
        if IsOperator(value) {
            after := numStack.Pop()  // 栈顶
            before := numStack.Pop() // 次顶
            num := CalcValue(before.(float32), after.(float32), value)
            numStack.Put(num)
        } else {
            num, _ := strconv.ParseFloat(value, 32)
            numStack.Put(float32(num))
        }
    }

    fmt.Println(numStack.Pop())
}