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.
1using System;
2using System.Collections.Generic;
3
4public class BasicCalculatorII {
5 public int Calculate(string s) {
6 Stack<int> stack = new Stack<int>();
7 char sign = '+';
8 int num = 0;
9 for (int i = 0; i < s.Length; i++) {
10 char c = s[i];
11 if (Char.IsDigit(c)) {
12 num = num * 10 + (c - '0');
13 }
14 if (!Char.IsDigit(c) && c != ' ' || i == s.Length - 1) {
15 if (sign == '+') {
16 stack.Push(num);
17 } else if (sign == '-') {
18 stack.Push(-num);
19 } else if (sign == '*') {
20 stack.Push(stack.Pop() * num);
21 } else if (sign == '/') {
22 stack.Push(stack.Pop() / num);
23 }
24 sign = c;
25 num = 0;
26 }
27 }
28
29 int result = 0;
30 while (stack.Count != 0) {
31 result += stack.Pop();
32 }
33 return result;
34 }
35
36 public static void Main() {
37 BasicCalculatorII calculator = new BasicCalculatorII();
38 Console.WriteLine("Output: " + calculator.Calculate("3+2*2"));
39 }
40}This C# solution iterates over characters, computes numeric values, uses a Stack to handle precedence, immediately processes '*' and '/' operations, appends '+' and '-' directly after converting to proper signs, and computes the final result by accumulating all 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.
1public class BasicCalculator {
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.