Coding

Basic Calculator III

Asked at

Goldman Sachs

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. 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 [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Input: s = "1+1" Output: 2

Input: s = "6-4/2" Output: 4

Input: s = "2*(5+5*2)/3+(6/2+8)"

1 <= s <= 104 s consists of digits, '+', '-', '*', '/', '(', and ')'. s is a valid expression.

cpp

class Solution {

public:
    int calculate(string s) {
        //User Code goes here
    }
};

java

class Solution {
    public int calculate(String s) {
        // User Code goes here
        return 0;
    }
}

python

class Solution:
    def calculate(self, s: str) -> int:
        # User Code goes here
        return 0

javascript

class Solution {
    calculate(s) {
        // User Code goes here
        return 0;
    }
}

csharp

public class Solution {
    public int Calculate(string s) {
        //User Code goes here
    }
};

func calculate(s string) int { }

Stuck? Show a way to structure it+

01Define integer-division behavior and whitespace handling
02Scan digits into complete numbers
03Recurse for parenthesized subexpressions
04Apply operators with precedence and return at closing parenthesis

Reference answer

Start by restating the input contract for Basic Calculator III and testing the smallest boundary case before choosing the algorithm. Parse with recursive descent or two stacks. A robust recursive approach maintains a number, a pending operator, and a stack for multiplication/division; when encountering '(', recursively evaluate until ')'. Apply addition/subtraction after resolving higher-precedence operations. Explain the invariant while coding, then show how each update preserves it. A single parse is O(n) time and O(n) space in the worst case for operators and nested parentheses. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How would you support exponentiation?
Tests: follow-up reasoning
How do you report malformed expressions?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question