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.
1function calculate(s) {
2 let stack = [];
3 let num = 0;
4 let sign = '+';
5
6 for (let i = 0; i < s.length; i++) {
7 if (!isNaN(s[i]) && s[i] !== ' ') {
8 num = num * 10 + parseInt(s[i]);
9 }
10 if (isNaN(s[i]) && s[i] !== ' ' || i === s.length - 1) {
11 if (sign === '+') {
12 stack.push(num);
13 } else if (sign === '-') {
14 stack.push(-num);
15 } else if (sign === '*') {
16 stack.push(stack.pop() * num);
17 } else if (sign === '/') {
18 stack.push(Math.trunc(stack.pop() / num));
19 }
20 sign = s[i];
21 num = 0;
22 }
23 }
24
25 return stack.reduce((a, b) => a + b);
26}
27
28console.log('Output:', calculate('3+2*2'));This JavaScript solution works by iterating over each character, computes numeric values, mutates the stack based on operator precedence with immediate execution for '*', '/' and posts calculation for '+' and '-', finally aggregates 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 Java solution focuses on efficiency by keeping track of only necessary information for computation: current number, last computed number, and current result. It simplifies calculations avoiding extra space usage.