栈实现四则远算

总结

四则运算表达式求值分两步
中缀转后缀，栈中存符号
后缀算结果，栈中存数字

中缀表达式与后缀表达式转换

中缀表达式1+(2-3)*4+5/6
后缀表达式1,2,+
通过栈进行转换

数字：直接输出
（：进栈
）：出栈直到（,弹出(
运算符：出栈（高阶等阶运算符），进栈（当前运算符）

#当前字符：1+(2-3)*4+5/6
#输出：1
#栈：
#当前字符：+(2-3)*4+5/6
#输出：1
#栈：+
#当前字符：(2-3)*4+5/6
#输出：1
#栈：+,(
#当前字符：2-3)*4+5/6
#输出：1,2
#栈：+,(
#当前字符：-3)*4+5/6
#输出：1,2
#栈：+,(,-
#当前字符：3)*4+5/6
#输出：1,2,3
#栈：+,(,-
#当前字符：)*4+5/6
#输出：1,2,3,-
#栈：+
#当前字符：*4+5/6
#输出：1,2,3,-,
#栈：+(低阶不弹出),*
#当前字符：4+5/6
#输出：1,2,3,-,4
#栈：+,*
#当前字符：+5/6
#输出：1,2,3,-,4,*(高阶弹出),+(等阶弹出)
#栈：+
#当前字符：5/6
#输出：1,2,3,-,4,*,+,5
#栈：+
#当前字符：/6
#输出：1,2,3,-,4,*,+,5
#栈：+,/
#当前字符：6
#输出：1,2,3,-,4,*,+,5,6
#栈：+,/
#当前字符：
#输出：1,2,3,-,4,*,+,5,6,/,+
#栈：
#1+(2-3)*4+5/6

后缀表达式的计算

数字进栈，符号远算

#[1,[[[2,3,-],4,*],[5,6,/],+],+]
#2-3=-1
#-1*4=-4
#5/6=0.833
#-4+0.833=-3.167
#1+(-3.167)=-2.167

python实现

def calculator(s: str) -> float:
    s = s.replace(" ", "")
    s_list = []
    for c in list(s):
        if c.isdigit():
            if len(s_list) == 0 or isinstance(s_list[-1], str):
                s_list.append(int(c))
            else:
                s_list[-1] *= 10+int(c)
        else:
            s_list.append(c)
    # 中缀转后缀
    stack = []
    s_end = []
    for c in s_list:
        if isinstance(c, int):
            s_end.append(c)
        elif c == "(":
            stack.append(c)
        elif c == ")":
            while stack[-1] != "(":
                s_end.append(stack.pop())
            stack.pop()
        elif c in ["*", "/"]:
            while len(stack) != 0 and stack[-1] in ["*", "/"]:
                s_end.append(stack.pop())
            stack.append(c)
        elif c in ["+", "-"]:
            while len(stack) != 0 and stack[-1] in ["+", "-", "*", "/"]:
                s_end.append(stack.pop())
            stack.append(c)
        else:
            continue
    while stack:
        s_end.append(stack.pop())
    print(s_end)
    # 计算后缀表达式
    stack = []
    for c in s_end:
        if isinstance(c, int):
            stack.append(c)
        elif c == "+":
            stack[-2] += stack[-1]
            stack.pop()
        elif c == "-":
            stack[-2] -= stack[-1]
            stack.pop()
        elif c == "*":
            stack[-2] *= stack[-1]
            stack.pop()
        elif c == "/":
            stack[-2] /= stack[-1]
            stack.pop()
        else:
            continue
    return stack[0]

if __name__ == "__main__":
    print(calculator("1+(2-3)*4+5/6"))

栈实现四则远算

总结

中缀表达式与后缀表达式转换

后缀表达式的计算

python实现

leetcode相关题目