Basic Calculator III - Practice Coding Problems

Basic Calculator III - Problem

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only:

Non-negative integers
'+', '-', '*', '/' operators
Open '(' and closing parentheses ')'

Important notes:

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³¹, 2³¹ - 1]
You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval()

Input & Output

Example 1 — Basic Expression with Parentheses

$ Input: s = "1 + 1"

› Output: 2

💡 Note: Simple addition: 1 + 1 = 2

Example 2 — Complex Expression with All Operations

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

› Output: 4

💡 Note: Following order of operations: 6 - (4/2) = 6 - 2 = 4

Example 3 — Nested Parentheses

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

› Output: 21

💡 Note: Step by step: 2*(5+10)/3+(3+8) = 2*15/3+11 = 30/3+11 = 10+11 = 21

Constraints

1 ≤ s.length ≤ 3 × 10⁴
s consists of integers and operators ('+', '-', '*', '/', '(', ')') separated by some number of spaces
s represents a valid expression
All intermediate results will be in the range of [-2³¹, 2³¹ - 1]
You are guaranteed that no division by zero will occur

Visualization

Tap to expand

Understanding the Visualization

Input

Mathematical expression string with numbers, operators, and parentheses

Parse

Process expression respecting operator precedence and parentheses

Output

Computed integer result

Key Takeaway

🎯 Key Insight: Use stack-based parsing to naturally handle operator precedence and recursion for parentheses

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 25

The key insight is to use a stack-based approach that handles operator precedence naturally. Parse the expression left-to-right, using the stack to manage operands while applying operators based on precedence rules. For parentheses, use recursion to evaluate sub-expressions. Best approach is Stack-Based Evaluation with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Evaluation	O(n)	O(n)	Use stack to handle operators by precedence and parentheses systematically
Recursive Parsing with Multiple Passes	O(n²)	O(n)	Parse expression recursively, handling parentheses with separate function calls

Stack-Based Evaluation — Algorithm Steps

Step 1: Parse numbers and push to operand stack
Step 2: Handle operators based on precedence using operator stack
Step 3: Process parentheses with recursive evaluation
Step 4: Apply remaining operations and return result

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Numbers

Build numbers digit by digit

Handle Operators

Apply based on precedence using stack

Process Parentheses

Recursive evaluation of sub-expressions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int calculate(char* s);

int solution(char* s) {
    // Remove spaces
    char* cleaned = malloc(strlen(s) + 1);
    int j = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] != ' ') {
            cleaned[j++] = s[i];
        }
    }
    cleaned[j] = '\0';
    
    int result = calculate(cleaned);
    free(cleaned);
    return result;
}

int calculate(char* s) {
    int stack[1000];
    int top = -1;
    int num = 0;
    char sign = '+';
    int i = 0;
    int len = strlen(s);
    
    while (i < len) {
        char c = s[i];
        
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        }
        
        if (c == '(') {
            int count = 1;
            int j = i + 1;
            while (count > 0) {
                if (s[j] == '(') count++;
                else if (s[j] == ')') count--;
                j++;
            }
            
            char* substr = malloc(j - i);
            strncpy(substr, s + i + 1, j - i - 2);
            substr[j - i - 2] = '\0';
            
            num = calculate(substr);
            free(substr);
            i = j - 1;
        }
        
        if (c == '+' || c == '-' || c == '*' || c == '/' || i == len - 1) {
            if (sign == '+') {
                stack[++top] = num;
            } else if (sign == '-') {
                stack[++top] = -num;
            } else if (sign == '*') {
                stack[top] = stack[top] * num;
            } else if (sign == '/') {
                stack[top] = stack[top] / num;
            }
            
            sign = c;
            num = 0;
        }
        
        i++;
    }
    
    int result = 0;
    for (int k = 0; k <= top; k++) {
        result += stack[k];
    }
    
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with constant time stack operations

✓ Linear Growth

Space Complexity

O(n)

Stack space for operators and operands, plus recursion depth

⚡ Linearithmic Space

78.0K Views

High Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Evaluation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler