LeetCode 솔루션

[11/20] 224. Basic Calculator

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.11.20 11:08

6,627 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

Hard

4893367Add to ListShare

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

Accepted

354,605

Submissions

841,931

#Amazo, #Google, #Microsoft, #ByteDance, #DoorDash, #Bloomberg, #Apple, #Hotstar

링크

https://leetcode.com/problems/basic-calculator/ 785 회 연결

익명
작성일 2022.11.20 11:27

Runtime: 229 ms, faster than 42.49% of Python3 online submissions for Basic Calculator.
Memory Usage: 18.1 MB, less than 9.85% of Python3 online submissions for Basic Calculator.

class Solution:
    def calculate(self, s: str) -> int:
        s = list(s)
        stack = []
        
        def calc(op, num):
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
        
        operators = ["+","-"]
        op = "+"
        num = 0
        
        for char in s+["+"]:
            
            if char in operators:
                calc(op, num)
                op = char
                num = 0
            elif char.isdigit():
                num = num*10 + int(char)
            
            elif char == "(":
                stack.append(op)
                op = "+"
                num = 0
                
            elif char == ")":
                calc(op, num)
                op = "+"
                num = 0
                temp = 0
                while stack[-1] not in operators:
                    temp += stack.pop()
                
                temp_op = stack.pop()
                calc(temp_op, temp)
                
        return sum(stack)

Runtime: 229 ms, faster than 42.49% of Python3 online submissions for Basic Calculator.
Memory Usage: 18.1 MB, less than 9.85% of Python3 online submissions for Basic Calculator.
[code=Python 3]class Solution:
    def calculate(self, s: str) -> int:
        s = list(s)
        stack = []
        
        def calc(op, num):
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
        
        operators = ["+","-"]
        op = "+"
        num = 0
        
        for char in s+["+"]:
            
            if char in operators:
                calc(op, num)
                op = char
                num = 0
            elif char.isdigit():
                num = num*10 + int(char)
            
            elif char == "(":
                stack.append(op)
                op = "+"
                num = 0
                
            elif char == ")":
                calc(op, num)
                op = "+"
                num = 0
                temp = 0
                while stack[-1] not in operators:
                    temp += stack.pop()
                
                temp_op = stack.pop()
                calc(temp_op, temp)
                
        return sum(stack)[/code]