Sponsored
Sponsored
This approach uses a stack to store numbers and consider operator precedence. Multiplication and division are processed immediately, whereas addition and subtraction modify how numbers are pushed onto the stack.
Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack.
1class BasicCalculatorII:
2 def calculate(self, s: str) -> int:
3 stack = []
4 num = 0
5 sign = '+'
6
7 for i, char in enumerate(s):
8 if char.isdigit():
9 num = num * 10 + int(char)
10 if char in '+-*/' or i == len(s) - 1:
11 if sign == '+':
12 stack.append(num)
13 elif sign == '-':
14 stack.append(-num)
15 elif sign == '*':
16 stack[-1] *= num
17 elif sign == '/':
18 stack[-1] = int(stack[-1] / num) # use int() to truncate toward zero in Python
19 num = 0
20 sign = char
21
22 return sum(stack)
23
24calculator = BasicCalculatorII()
25print("Output:", calculator.calculate("3+2*2"))This Python solution processes the string to calculate values, storing results in a stack. It evaluates '*' and '/' immediately with the stack's last value, pushes '+' and '-' results onto the stack, and finally returns the sum of stack values.
This approach parses the expression twice, first to handle multiplications and divisions, then to process additions and subtractions. This avoids using a stack and simplifies sign handling.
Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types.
1
This JavaScript approach processes the expression by altering last computed numbers in-place while tracking only current and last numbers, efficiently managing space and resources.