TikTok 计算器：整数四则、括号与一元负号怎样解析？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练允许ASCII整数、空白、+−*/、括号与一元+−，不支持浮点、变量或隐式乘法。
• 除法向零取整，除零报错；不把Python负数//的向下取整当默认题意。
• 所有输入必须被完整消费，空式与语法错误报ValueError。嵌套过深会触及Python递归限制，可改显式栈。

解题路线

1. 文法分三层：expression为term之间的加减，term为factor之间的乘除，factor为可带一元符号的整数或括号式。优先级由调用层级表达，不能见到运算符就按字符先后全部左算。
2. 同一层用循环从左向右组合，保持二元运算左结合；8/3*3先得2再得6，不能把右半部分递归成3*3再除。括号内部重新调用expression直到遇右括号。
3. 一元符号只在factor开始读，比如2*−3与−(1+2)。本文连续符号按奇偶翻转sign，1−−2也合法；如正式只允许单个符号，须收紧语法。
4. 整数向零除法取abs(a)//abs(b)，再按符号恢复。不要先用float做除法再int，大整数可能损失精度甚至溢出；比较−7/3的预期可快速核定合同。
5. 解析一个数后碰到另一个数或左括号，要保留位置直到外层完整检查，不能静默接受1 2或2(3)。缺右括号、空括号、尾运算符需要明确报错，而不是返回部分结果。
6. 复杂度证明要按字符指针：每个token由一次对应层处理，position只向前；一次嵌套返回不重新扫描括号内容。正则预切token也可用，但不应在递归中不断复制整段子字符串。
7. 手写测试先覆盖优先级、结合性、负商、空白、大整数、边界括号与非法式。独立对照用Python AST作为另一解析器，再按有理数向零截断求值，避免eval任意输入。

手动走一遍

2*−(3+4)+5结果−9；8/3*3结果6；−7/3结果−2，而Python −7//3为−3。2(3)不是乘法简写，1+和()不是合法式，均应拒绝。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""ASCII integer expression grammar, unary +/-, parentheses, truncating division.
No implicit multiplication. Empty/malformed expressions raise ValueError.
"""


def calculate(text):
    position = 0

    def spaces():
        nonlocal position
        while position < len(text) and text[position].isspace():
            position += 1

    def factor():
        nonlocal position
        spaces()
        sign = 1
        while position < len(text) and text[position] in '+-':
            if text[position] == '-':
                sign = -sign
            position += 1
            spaces()
        if position < len(text) and text[position] == '(':
            position += 1
            value = expression()
            spaces()
            if position >= len(text) or text[position] != ')':
                raise ValueError('missing closing parenthesis')
            position += 1
            return sign * value
        start = position
        while position < len(text) and '0' <= text[position] <= '9':
            position += 1
        if position == start:
            raise ValueError('integer or parenthesis expected')
        return sign * int(text[start:position])

    def term():
        nonlocal position
        value = factor()
        while True:
            spaces()
            if position >= len(text) or text[position] not in '*/':
                return value
            op = text[position]
            position += 1
            right = factor()
            if op == '*':
                value *= right
            else:
                if right == 0:
                    raise ZeroDivisionError('division by zero')
                quotient = abs(value) // abs(right)
                value = -quotient if (value < 0) != (right < 0) else quotient

    def expression():
        nonlocal position
        value = term()
        while True:
            spaces()
            if position >= len(text) or text[position] not in '+-':
                return value
            op = text[position]
            position += 1
            right = term()
            value = value + right if op == '+' else value - right

    answer = expression()
    spaces()
    if position != len(text):
        raise ValueError('unexpected trailing input')
    return answer

复杂度

忽略大整数算术成本时O(L)时间，递归栈O(D)，D为括号/递归嵌套深度；中间整数位数由输入与运算增长决定，不能把任意精度乘除称作常量成本。

易错点与追问

容易失分的边界

• 把乘除与加减同级。
• 负数除法使用//直接取整。
• 只解析前半段而不检查尾部。
• 递归复制括号子串造成二次开销。

继续深挖

• 如果不允许unary怎样收紧factor？
• 怎样换为两个栈避免递归深度限制？
• 需要输出错误位置怎么保留token span？
• 允许浮点或变量后哪些合同要重新定？