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 -
sconsists of digits,'+','-','(',')', and' '. -
srepresents 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.
SOLUTION:
class Solution:
def eval(self, a, op, b):
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '/':
return int(a / b)
elif op == '*':
return a * b
def calculate(self, s: str) -> int:
s += " "
precedence = {
'*': 1,
'/': 1,
'+': 0,
'-': 0
}
brackets = {
'(': 1,
')': -1
}
numstack = []
opstack = []
chunk = ""
latestOpenBracket = True
for c in s:
if c == " " or c in precedence or c in brackets:
if len(chunk) > 0:
numstack.append(int(chunk))
chunk = ""
if c in brackets:
if brackets[c] == 1:
opstack.append('(')
latestOpenBracket = True
elif brackets[c] == -1:
latestOpenBracket = False
while opstack[-1] != '(':
currop = opstack.pop()
b = numstack.pop()
a = numstack.pop()
res = self.eval(a, currop, b)
numstack.append(res)
opstack.pop()
elif c in precedence:
if latestOpenBracket:
numstack.append(0)
while len(opstack) > 0 and precedence.get(opstack[-1], -1) >= precedence[c]:
currop = opstack.pop()
b = numstack.pop()
a = numstack.pop()
res = self.eval(a, currop, b)
numstack.append(res)
opstack.append(c)
latestOpenBracket = False
else:
chunk += c
latestOpenBracket = False
while len(opstack) > 0:
currop = opstack.pop()
b = numstack.pop()
a = numstack.pop()
res = self.eval(a, currop, b)
numstack.append(res)
return numstack[0]
Top comments (0)