面试题 16.26. 计算器

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， – ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 1

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

Python 解答：
1.堆栈

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        slist = []
        i = 0 
        while i < len(s):
            if s[i] == ' ':
                i += 1
            elif s[i].isdigit():
                j = i 
                while j < len(s) and s[j].isdigit():
                    j += 1
                slist.append(s[i:j])
                i = j
            else:
                slist.append(s[i])
                i += 1
        while slist:
            c = slist.pop(0)
            if c.isdigit():
                stack.append(int(c))
            elif c == '+' or c == '-':
                stack.append(c)
            elif c == '*' or c == '/':
                left = stack.pop()
                right = slist.pop(0)
                if c == '*':
                    stack.append(int(left)*int(right))
                else:
                    stack.append(int(left)//int(right))
        result = 0
        while stack:
            c = stack.pop(0)
            if type(c) == int:
                result += c
            elif c == '+' or c == '-':
                right = stack.pop(0)
                if c == '+':
                    result += right
                else:
                    result -= right
        return result