栈实现四则远算

2020 年 3 月 26 日 星期四
/
10

栈实现四则远算

总结

四则运算表达式求值分两步:

  1. 中缀转后缀,栈中存符号

  2. 后缀算结果,栈中存数字

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

中缀表达式1+(2-3)*4+5/6

后缀表达式1,2,+

通过栈进行转换

当前字符串后缀表达式
1+(2-3)*4+5/6
+(2-3)*4+5/61
(2-3)*4+5/61+
2-3)*4+5/61+(
-3)*4+5/612+(
3)*4+5/612+(-
)*4+5/6123+(-
*4+5/6123-+
4+5/6123-+*
+5/6123-4+*
5/6123-4*++
/6123-4*+5+
6123-4*+5+/
123-4*+56+/
123-4*+56/+

后缀表达式的计算

数字进栈,符号远算

[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/

评论已关闭