Microsoft OA 面试真题解析：Basic Calculator（带括号的四则运算）

题目描述

实现一个计算器，计算给定字符串中的数学表达式。表达式包含非负整数、加减乘除四则运算和括号。要求正确处理运算优先级与括号嵌套。

解题思路

用两个栈：数字栈和运算符栈。遇到数字读完整再入栈；遇到运算符时，先把栈顶优先级不低于它的运算符弹出计算，再压入新运算符；遇到左括号压栈，遇到右括号一直弹到左括号。最后清空运算符栈。

def calculate(s):
    def apply(op, a, b):
        if op == '+': return a + b
        if op == '-': return a - b
        if op == '*': return a * b
        return int(a / b)  # 整除按题意

    def prec(op):
        return 2 if op in '*/' else 1

    nums, ops = [], []
    i = 0
    while i < len(s):
        c = s[i]
        if c.isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            nums.append(int(s[i:j]))
            i = j
            continue
        if c in '+-*/':
            while ops and ops[-1] != '(' and prec(ops[-1]) >= prec(c):
                b = nums.pop(); a = nums.pop()
                nums.append(apply(ops.pop(), a, b))
            ops.append(c)
        elif c == '(':
            ops.append(c)
        elif c == ')':
            while ops[-1] != '(':
                b = nums.pop(); a = nums.pop()
                nums.append(apply(ops.pop(), a, b))
            ops.pop()
        i += 1
    while ops:
        b = nums.pop(); a = nums.pop()
        nums.append(apply(ops.pop(), a, b))
    return nums[-1]

复杂度与易错点

时间 O(n)，空间 O(n)。除法的取整方向（向零、向下）和负数结果要提前确认；读多位数时要把指针一次推进到数字末尾，避免逐字符重复入栈。

FAQ

除法为什么要单独确认取整方向？

不同语言的整数除法行为不同（如 Python 的 // 是向下取整），题面若要求向零取整，需要用 int(a / b) 或用符号修正，否则负数场景会出错。

参考来源

• LeetCode 224 — Basic Calculator
• LeetCode 772 — Basic Calculator III

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。