Skip to content

Latest commit

 

History

History
121 lines (81 loc) · 4.49 KB

0224._Basic_Calculator.md

File metadata and controls

121 lines (81 loc) · 4.49 KB

224. Basic Calculator

难度: Hard

刷题内容

原题连接

内容描述

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2
Example 2:

Input: " 2-1 + 2 "
Output: 3
Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

基本跟227一样，只是这里加了括号

瞄了一眼，基本上infix(中缀表达式)都是表达成postfix(后缀表达式)再来求值的。 比如 A + B * C 写成 A B C * +

Infix Expression Prefix Expression Postfix Expression
A + B + A B A B +
A + B * C + A * B C A B C * +

infix 中缀转postfix 后缀还有专门的算法：https://en.wikipedia.org/wiki/Shunting-yard_algorithm

  1. Create an empty stack called opstack for keeping operators. Create an empty list for output.

  2. Convert the input infix string to a list by using the string method split.

  3. Scan the token list from left to right.

    • If the token is an operand, append it to the end of the output list.
    • If the token is a left parenthesis, push it on the opstack.
    • If the token is a right parenthesis, pop the opstack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
    • If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.

  5. When the input expression has been completely processed, check the opstack. Any operators still on the stack can be removed and appended to the end of the output list.

可以看到中缀转后缀一个重要的点是： 当我们把operator +-*/ 放到opstack上时候，我们需要考虑/看是否有之前的operator有更高或者相等的precedence，这个时候我们需要优先（计算）把它放到output list.

参考

  1. 3.9. Infix, Prefix and Postfix Expressions
  2. southpenguin

Explanation

Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.

Only 5 possible input we need to pay attention:

  1. digit: it should be one digit from the current number
  2. '+': number is over, we can add the previous number and start a new number
  3. '-': same as above
  4. '(': push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
  5. ')': pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.

Finally if there is only one number, from the above solution, we haven't add the number to the result, so we do a check see if the number is zero.

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        res, num, sign = 0, 0, 1
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            elif c in '+-':
                res += sign * num
                num = 0
                sign = 1 if c == '+' else -1
            elif c == '(': # push the result first, then sign;
                stack.append(res)
                stack.append(sign)
                res, sign = 0, 1 # reset the sign and res for the value in the parenthesis
            elif c == ')': # use elif because there may have space in input s
                res += sign * num # temporary res in this parenthesis
                num = 0
                res *= stack.pop() # sign before the left parenthesis
                res += stack.pop() # res calculated before the left parenthesis
        return res if num == 0 else res + sign * num