A billing pipeline stored invoice line formulas as spreadsheet cells: integers and + - * /, optional spaces, no parentheses. Finance signed off that 3+2*2 must be 7, not a left-to-right 10. The first version split the string and folded every operator as it appeared. Staging invoices with only plus signs matched the ledger. The first mixed * in production priced a line at the wrong total.
Basic Calculator II asks you to evaluate infix with precedence and no parentheses. A left-to-right fold uses the operators and still ignores that * / bind tighter. Rebuilding a parenthesized string and eval-ing it is the wrong interview bill — Java has no eval, and this prompt forbids parentheses anyway.
This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about pending terms so multiply and divide can collapse the last one before plus and minus are summed. Postfix already has operators in evaluation order — that is Reverse Polish. This prompt is infix with precedence, no parens.
The problem
Given a string s of non-negative integers and the operators +, -, *, and /, with optional spaces and no parentheses, evaluate the expression and return the integer result. * and / bind tighter than + and -. Division truncates toward zero. The expression is valid: no divide-by-zero, and every intermediate fits in a 32-bit int.
s = "3+2*2" → 7
s = " 3/2 " → 1
s = "3+5 / 2" → 5
s = "14-3/2" → 13Note: Multi-digit numbers are one integer, not digits to add. Spaces are noise. 14-3/2 is 14 - (3/2) → 13, not left-to-right (14-3)/2 as 5 or 5.5. Java int division already truncates toward zero — you do not call Math.floor.
Tokenize then two-pass is the honest brute force
Scan once into numbers and operators. A first pass reduces every * / pair in place. A second pass folds leftover + - left to right. Correct. That is also a short walk from emitting postfix and calling the Reverse Polish fold — that sibling already owns postfix; do not re-solve it here.
int calculateTwoPass(String s) {
List<Integer> nums = new ArrayList<>();
List<Character> ops = new ArrayList<>();
int n = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') {
continue;
}
if (Character.isDigit(c)) {
n = n * 10 + (c - '0');
} else {
nums.add(n);
n = 0;
ops.add(c);
}
}
nums.add(n);
List<Integer> terms = new ArrayList<>();
List<Character> plusMinus = new ArrayList<>();
terms.add(nums.get(0));
for (int i = 0; i < ops.size(); i++) {
char op = ops.get(i);
int rhs = nums.get(i + 1);
if (op == '*') {
int last = terms.size() - 1;
terms.set(last, terms.get(last) * rhs);
} else if (op == '/') {
int last = terms.size() - 1;
terms.set(last, terms.get(last) / rhs);
} else {
plusMinus.add(op);
terms.add(rhs);
}
}
int acc = terms.get(0);
for (int i = 0; i < plusMinus.size(); i++) {
acc = plusMinus.get(i) == '+'
? acc + terms.get(i + 1)
: acc - terms.get(i + 1);
}
return acc;
}At n = 20 the extra lists are a rounding error. At n in the hundreds of thousands you still paid a tokenize and a second pass for a question a stack answers while you parse: apply the previous sign to the number we just finished?
Apply the previous sign; multiply and divide collapse now
Walk left to right. Accumulate a multi-digit number. Skip spaces. When you hit an operator — or the end of the string — apply the previous sign to the number you just finished:
+pushn-push-n*pop, pushpop * n/pop, pushpop / n(toward zero)
Then remember the character you just saw as the new previous sign. The first previous sign is +. At the end, sum the stack.
s = "3+2*2" prev = '+'
3 n=3
+ apply '+': push 3 stack: 3 prev='+'
2 n=2
* apply '+': push 2 stack: 3 2 prev='*'
2 n=2
end apply '*': pop 2 * 2 = 4 stack: 3 4
sum → 7
s = "14-3/2" prev = '+'
14 n=14
- apply '+': push 14 stack: 14 prev='-'
3 n=3
/ apply '-': push -3 stack: 14 -3 prev='/'
2 n=2
end apply '/': pop -3 / 2 = -1 stack: 14 -1
sum → 13The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack.
int calculate(String s) {
Deque<Integer> terms = new ArrayDeque<>();
int n = 0;
char prev = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
n = n * 10 + (c - '0');
}
if (c == '+' || c == '-' || c == '*' || c == '/'
|| i == s.length() - 1) {
switch (prev) {
case '+':
terms.push(n);
break;
case '-':
terms.push(-n);
break;
case '*':
terms.push(terms.pop() * n);
break;
default:
terms.push(terms.pop() / n);
break;
}
prev = c;
n = 0;
}
}
int ans = 0;
for (int t : terms) {
ans += t;
}
return ans;
}Time is O(n) — one pass, one push or one pop-push per operator. Space is O(n) for pending terms (worst case the expression is all + and -). The prompt promised a valid expression, so the stack is never empty on * / and the sum is the answer.
Note: The sign you apply is the previous operator. Finish the current number, apply prev, then remember the character you just saw. Spaces are not operators; if you flush on a space you push 0 and wipe a pending term. The last number has no trailing operator — apply prev when the index hits the end of the string, including a trailing space.
What interviewers usually poke next
- Parentheses. That is a different prompt (Basic Calculator I). Nested
+-needs a second stack or a recursive descent; do not start that walk when this string has no parens. - Unary minus. A leading
-, or-after another operator, is a sign, not subtraction. This prompt’s integers are non-negative; say so before you invent a state. - Toward-zero division. Java
intdivision is the spec.Math.floorof a negative quotient goes the other way;14-3/2is13because(-3)/2is-1, not a float5.5. - Postfix instead. Emitting RPN and folding it is the Reverse Polish sibling. Connect the two if they ask; do not re-solve postfix on this board.
- Invalid tokens / missing operands. The prompt forbids it. In production you would reject; at the board, ask.
You are done with this problem when you can apply the previous sign as each number finishes, collapse * / on the top term, and refuse both left-to-right eval and a postfix rewrite.