栈实现四则远算

总结

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

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

中缀表达式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"))

leetcode相关题目

1.https://leetcode.com/problems/basic-calculator/
2.https://leetcode.com/problems/basic-calculator-ii/
3.https://leetcode.com/problems/basic-calculator-iii/
4.https://leetcode.com/problems/basic-calculator-iv/