逆波兰表示法

运算规则

四则运算法则是“先乘除，后加减，从左至右，先括号内后括号外”。但是当乘除出现在加减的后面，或者表达式中有括号出现，编程处理起来就比较麻烦。对于括号的处理，因为括号永远是成对匹配的，可以用栈结构，遇到左括号就进栈，遇到右括号就让栈顶的左括号出栈，并对这期间的数字运算。对于先乘除后加减的处理，波兰的Jan Łukasiewicz提出了一种后缀表示法——逆波兰表示。

规则：从左向右遍历表达式的每一个数字和运算符号，遇到数字，进栈，遇到符号，将栈顶的两个数字出栈运算，运算结果进栈，直到获得最终结果。

对于运算式\(1+(3-2)\times 4 + 10 / 5\)，用后缀表达法表示为1 3 2 - 4* + 10 5 /+，运算流程如下

1. 初始化空栈；
2. 1,3,2均为数字，进栈；
3. 遇到-，将2,3出栈，3作为被减数，2作为减数，得到差是1进栈；
4. 4进栈；
5. 遇到×，1,4出栈，乘积是4，进栈；
6. 遇到+，1，4出栈，和是5，进栈；
7. 10,5进栈；
8. 遇到/10作为被除数，5作为除数，商是2，进栈；
9. 最后，5,2出栈，和是7，最终运算结果是7；

这种运算虽然流程比较麻烦，但适合计算机处理四则运算。

代码实现

# coding:utf-8
def calculatePostfix(postfix: str) -> int:
    """Evaluation of postfix expressions"""
    stack = []
    for i in postfix:
        if i in "+-*/":
            value_2 = int(stack.pop())
            value_1 = int(stack.pop())
            if i == "+":
                result = value_1 + value_2
            elif i == "-":
                result = value_1 - value_2
            elif i == "*":
                result = value_1 * value_2
            else:
                result = value_1 // value_2
            stack.append(result)
        else:
            stack.append(i)
    return stack.pop()

怎样识别多位数呢？

中缀表达式转为后缀表达式

平常使用的表达式称为中缀表达式，要将其转化为后缀表达式方便计算机运算。

规则：遍历中缀表达式的每一个数字和符号，遇到数字输出，遇到运算符号，将其与栈顶符号比较优先级，若优先级低或者是)，则栈顶元素出栈并输出，当前符号进栈

将\(1+(3-2)\times 4 + 10 / 5\)转化为后缀表达法表示为1 3 2 - 4* + 10 5 /+，流程如下

1. 初始化空栈，用于处理符号；
2. 输出1，将+进栈
3. (进栈，
4. 3是数字，输出
5. -进栈，输出2
6. )匹配(，将-输出，
7. *进栈，输出4
8. +优先级低，输出*，+，+进栈
9. 输出10,5
10. /优先级高于+，输出/，
11. 输出+

最终得到后缀表达式1 3 2 - 4* + 10 5 /+

代码实现

# coding:utf-8
def priority(i: str) -> int:
    if i in ["*", "/"]:
        return 2
    elif i in ["+", "-"]:
        return 1


def in2Postfix(infix: str) -> str:
    stack = []
    postfix = []
    for i in infix:
        if i not in ["×", "*", "/", "+", "-", "(", ")"]:
            postfix.append(i)
        else:
            if i != ")" and (not stack or i == "(" or stack[-1] == "(" or priority(i) > priority(stack[-1])):
                stack.append(i)
            elif i == ")":
                while True:
                    x = stack.pop()
                    if x != "(":
                        postfix.append(x)
                    else:
                        break
            else:
                while True:
                    if stack and stack[-1] != "(" and priority(i) <= priority(stack[-1]):
                        postfix.append(stack.pop())
                    else:
                        stack.append(i)
                        break
    while stack:
        postfix.append(stack.pop())

    return "".join(postfix)