algorithm - 评估字符串形式的数学表达式

Question

这是一个标准的面试问题，评估以字符串形式给出的数学表达式。

如此提供，'3+3-6*2'答案应该是-6

现在如果表达式只支持四种操作+,-,*,/那么有没有一种简单的方法可以使用堆栈来完成。

我已经通过将中缀符号转换为后缀符号然后使用堆栈解决它来解决它 - 但我正在寻找一种仅支持这四种操作的不同方法。这是我的解决方案，

def evaluate(self, s: str) -> int:
    expr = [i for i in re.split(r'(\d+|\W+)', s) if i]
    rpn = self.convertToPostfix(expr)
    return self.evalPostfix(rpn)

def convertToPostfix(self, infix: list) -> list:
    stack = collections.deque()
    result = []
    for item in infix:
        if item.isdigit():
            result.append(item)
        else:
            while len(stack) > 0 and self.has_higher_precedence(stack[-1], item):
                result.append(stack[-1])
                stack.pop()
            stack.append(item)
    while len(stack) > 0:
        result.append(stack.pop())
    return result

def has_higher_precedence(self, a: str, b: str) -> bool:
    if a == '/' and b == '*' or b == '+' or b == '-':
        return True
    if a == '*' and b == '+' or '-':
        return True
    if a == '+' and b == '-':
        return True
    return False

def evalPostfix(self, p: list) -> int:
    stack = collections.deque()
    for item in p:
        if item.isdigit():
            stack.append(int(item))
        elif item[1:].isdigit():
            stack.append(int(item))
        else:
            curr = stack.pop()
            prev = stack.pop()
            if item == '+':
                total = prev + curr
            elif item == '-':
                total = prev - curr
            elif item == '*':
                total = prev * curr
            else:
                total = prev / curr
            stack.append(total)
    return stack.pop()

另外我知道这可以通过设计递归词法解析器来解决，但这超出了这个问题的范围。

所以我的问题是，如果只有四个运算符，是否有一种简单的方法可以在 O(n) 时间内使用堆栈执行此操作

Answer 1

您可以将字符串存储为字符列表，然后线性运行它 2 次，首先计算乘法/除法，然后计算加法/减法。

即在第一次迭代中有

1+10/2 -> 1 + 5 

然后有

1 + 5 -> 6

这也可以很容易地通过堆栈实现，您可以在堆栈中添加带有 + 或 - 符号的数字。当您添加到堆栈并意识到您到达了 / 或 * 符号时，您弹出前一个元素，将其乘以或除以当前数字，然后将其压入后退。最后，您找到堆栈中所有元素的总和。

更进一步，您可以观察到在前面的示例中，使用的唯一堆栈元素是直接在答案之前的元素。这表明您可以在保持总和的同时存储前一个元素，如果到达 * 或 / 符号，则从总和中减去前一个元素并添加更新后的元素.该方法有效解决了一次O(n)扫描的问题，增加了O(1)的存储空间，可能是该问题的最优解。