Evaluate an Expression With Precedence, No Parentheses
Solve this Problems containing non-negative integers and the operators +, -, *, / — no parentheses — where multiplication and division bind tighter than addition and subtraction, and operators of equal precedence apply left to right.
The trick to handling precedence in one pass without ever building a parse tree: don't resolve an operator the moment it's seen — resolve the previous one, once its right-hand number is fully known. Track just one pending operator and the number being built. When a new operator (or the end of the string) arrives, apply the pending one: + and - simply push a (possibly negated) value; * and / instead pop whatever was pushed most recently and combine it immediately, so a tight-binding operation never lingers as two separate terms. By the end, every value left on the stack is already fully resolved, and the answer is just their sum.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 12 - ◆
s contains non-negative integers (possibly multi-digit) and the operators '+', '-', '*', '/' — no parentheses, no spaces - ◆
'*' and '/' bind tighter than '+' and '-', and operators of equal precedence apply left to right - ◆
Division truncates toward zero
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeatedly Reduce the First '*' or '/'
BruteRepeatedly scan for the first '*' or '/' anywhere in the string, extract the full numbers immediately on either side of it (a number can be multiple digits, so this means scanning outward until a non-digit is hit), compute that one operation, and splice the result back in as a plain number — shrinking the string. Repeat until no '*' or '/' remains, so every remaining operator is '+' or '-', which can just be summed left to right. Each reduction re-scans from the start and touches up to O(n) characters, and there can be up to n such reductions — O(n²) overall.
O(n²)O(n)1class Solution {
2 public int calculateII(String s) {
3 while (s.contains("*") || s.contains("/")) {
4 int opIdx = -1;
5 for (int i = 0; i < s.length(); i++) {
6 if (s.charAt(i) == '*' || s.charAt(i) == '/') { opIdx = i; break; }
7 }
8 int leftStart = opIdx - 1;
9 while (leftStart > 0 && Character.isDigit(s.charAt(leftStart - 1))) leftStart--;
10 int rightEnd = opIdx + 1;
11 while (rightEnd < s.length() && Character.isDigit(s.charAt(rightEnd))) rightEnd++;
12 int leftNum = Integer.parseInt(s.substring(leftStart, opIdx));
13 int rightNum = Integer.parseInt(s.substring(opIdx + 1, rightEnd));
14 int result = s.charAt(opIdx) == '*' ? leftNum * rightNum : leftNum / rightNum;
15 s = s.substring(0, leftStart) + result + s.substring(rightEnd);
16 }
17 return evalFlat(s);
18 }
19
20 private int evalFlat(String s) {
21 int result = 0, num = 0, sign = 1;
22 for (int i = 0; i <= s.length(); i++) {
23 char c = i < s.length() ? s.charAt(i) : '\0';
24 if (Character.isDigit(c)) {
25 num = num * 10 + (c - '0');
26 } else if (c == '+') {
27 result += sign * num; num = 0; sign = 1;
28 } else if (c == '-') {
29 result += sign * num; num = 0; sign = -1;
30 } else if (i == s.length()) {
31 result += sign * num;
32 }
33 }
34 return result;
35 }
36}Optimal — Single Pass With a Number Stack
OptimalWalk the string once, remembering only the operator that preceded the number currently being built. When a new operator (or the end of the string) is reached, resolve the *previous* operator against the number just finished: '+' pushes it as-is, '-' pushes its negation, and — the key trick — '*' and '/' pop the most recently pushed value, combine it with the current number immediately, and push that back, since a tighter-binding operation should collapse into a single term right away rather than waiting. Once every token has been processed this way, everything left on the stack is already sign-adjusted and can simply be summed.
O(n)O(n)1class Solution {
2 public int calculateII(String s) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 int num = 0;
5 char op = '+';
6 for (int i = 0; i <= s.length(); i++) {
7 char c = i < s.length() ? s.charAt(i) : '\0';
8 if (Character.isDigit(c)) {
9 num = num * 10 + (c - '0');
10 }
11 if ((c != '\0' && "+-*/".indexOf(c) >= 0) || i == s.length()) {
12 if (op == '+') stack.push(num);
13 else if (op == '-') stack.push(-num);
14 else if (op == '*') stack.push(stack.pop() * num);
15 else stack.push(stack.pop() / num);
16 op = c;
17 num = 0;
18 }
19 }
20 int total = 0;
21 while (!stack.isEmpty()) total += stack.pop();
22 return total;
23 }
24}