Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "3+2*2" Output: 7
Example 2:
Input: s = " 3/2 " Output: 1
Example 3:
Input: s = " 3+5 / 2 " Output: 5
Constraints:
1 <= s.length <= 3 * 105s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.s represents a valid expression.[0, 231 - 1].Basic Calculator II requires evaluating a mathematical expression string containing non‑negative integers and the operators +, -, *, and /. The main challenge is handling operator precedence while scanning the string efficiently.
A common approach is to iterate through the string while building the current number. When an operator or the end of the string is reached, process the previous operator. For addition and subtraction, push the number (or its negative) onto a stack. For multiplication and division, pop the last value from the stack, compute the result with the current number, and push it back. This ensures higher-precedence operations are evaluated immediately.
After processing the entire string, the final result is obtained by summing all values in the stack. This strategy avoids building a full expression tree and keeps the solution simple and efficient.
The algorithm runs in O(n) time since the string is scanned once, and uses O(n) space for the stack in the worst case.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based single pass evaluation | O(n) | O(n) |
Cracking FAANG
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.
1#include <iostream>
2#include <stack>
3
4int calculate(std::string s) {
5 std::stack<int> stack;
6 char sign = '+';
7 int num = 0;
8 for (size_t i = 0; i < s.length(); ++i) {
9 if (isdigit(s[i])) {
10 num = num * 10 + (s[i] - '0');
11 }
12 if (!isdigit(s[i]) && !isspace(s[i]) || i == s.length() - 1) {
13 if (sign == '+') {
14 stack.push(num);
15 } else if (sign == '-') {
16 stack.push(-num);
17 } else if (sign == '*') {
18 int top = stack.top();
19 stack.pop();
20 stack.push(top * num);
21 } else if (sign == '/') {
22 int top = stack.top();
23 stack.pop();
24 stack.push(top / num);
25 }
26 sign = s[i];
27 num = 0;
28 }
29 }
30
31 int result = 0;
32 while (!stack.empty()) {
33 result += stack.top();
34 stack.pop();
35 }
36 return result;
37}
38
39int main() {
40 std::string expression = "3+2*2";
41 std::cout << "Output: " << calculate(expression) << std::endl;
42 return 0;
43}This C++ solution utilizes the same logic with an std::stack to handle mutated values and precedence. It processes the input, modifies the stack during iterations, and sums the values at the end.
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"));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of expression evaluation problems like Basic Calculator II are commonly asked in FAANG and other top tech company interviews. They test understanding of stacks, parsing techniques, and handling operator precedence efficiently.
A stack is the most suitable data structure because it helps manage intermediate values and operator precedence. It allows multiplication and division to be resolved immediately while postponing addition and subtraction until the final summation.
The optimal approach uses a single pass through the string combined with a stack. Numbers are pushed for addition and subtraction, while multiplication and division are calculated immediately using the top of the stack to maintain correct operator precedence.
Multiplication and division have higher precedence than addition and subtraction. By resolving them immediately with the last stack value, we ensure the final summation of the stack correctly reflects the mathematical order of operations.
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.