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 public int Calculate(string s) {
int num = 0, lastNum = 0, result = 0;
char sign = '+';
int length = s.Length;
for (int i = 0; i < length; i++) {
char c = s[i];
if (Char.IsDigit(c)) {
num = num * 10 + (c - '0');
}
if (!Char.IsDigit(c) && c != ' ' || i == length - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum *= num;
} else if (sign == '/') {
lastNum /= num;
}
sign = c;
num = 0;
}
}
result += lastNum;
return result;
}
public static void Main() {
BasicCalculator calculator = new BasicCalculator();
Console.WriteLine("Output: " + calculator.Calculate("3+2*2"));
}
}This C# code optimally computes results using current and last numbers without extra data structures. Multiplications and divisions are handled inline, tracking operations on-the-fly.