Basic Calculator II - Practice Coding Problems

Basic Calculator II - Problem

Given a string s which represents a mathematical 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 [-2³¹, 2³¹ - 1].

Note: 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

$ Input: s = "3+2*2"

› Output: 7

💡 Note: Following order of operations: 2*2 = 4, then 3+4 = 7

Example 2 — Division with Truncation

$ Input: s = " 3/2 "

› Output: 1

💡 Note: 3 divided by 2 equals 1.5, but we truncate toward zero to get 1

Example 3 — Complex Expression

$ Input: s = " 3+5 / 2 "

› Output: 5

💡 Note: Division first: 5/2 = 2 (truncated), then 3+2 = 5

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 are in the range [-2³¹, 2³¹ - 1]
The divisor is never zero

Visualization

Tap to expand

Understanding the Visualization

Input

Mathematical expression as string: "3+2*2"

Process

Handle operator precedence: */÷ before +-

Output

Calculated result: 7

Key Takeaway

🎯 Key Insight: Use stack or variables to handle operator precedence naturally in one pass

Asked in

G Google 15 f Facebook 12 a Amazon 10 M Microsoft 8

The key insight is handling operator precedence by processing multiplication and division immediately while deferring addition and subtraction. The stack approach naturally handles this by storing intermediate results. Time: O(n), Space: O(n) for stack or O(1) for optimized approach.

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Evaluation	O(n)	O(n)	Parse expression twice: first for */, then for +-
Stack-Based Evaluation	O(n)	O(n)	Use stack to handle operator precedence in one pass
No Extra Space	O(n)	O(1)	Calculate result without using extra space

Two-Pass Evaluation — Algorithm Steps

Parse numbers and operators into tokens
First pass: evaluate all * and / operations
Second pass: evaluate all + and - operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse

Convert string to tokens

First Pass

Handle * and / operations

Second Pass

Handle + and - operations

Code -

solution.c — C

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

int solution(char* s) {
    char tokens[1000][20];
    int tokenCount = 0;
    int i = 0;
    
    while (s[i]) {
        if (s[i] == ' ') {
            i++;
            continue;
        }
        if (isdigit(s[i])) {
            int j = 0;
            while (s[i] && isdigit(s[i])) {
                tokens[tokenCount][j++] = s[i++];
            }
            tokens[tokenCount][j] = '\0';
            tokenCount++;
        } else {
            tokens[tokenCount][0] = s[i];
            tokens[tokenCount][1] = '\0';
            tokenCount++;
            i++;
        }
    }
    
    // First pass: handle * and /
    i = 1;
    while (i < tokenCount) {
        if (strcmp(tokens[i], "*") == 0) {
            int result = atoi(tokens[i-1]) * atoi(tokens[i+1]);
            sprintf(tokens[i-1], "%d", result);
            for (int j = i; j < tokenCount - 2; j++) {
                strcpy(tokens[j], tokens[j+2]);
            }
            tokenCount -= 2;
        } else if (strcmp(tokens[i], "/") == 0) {
            int result = atoi(tokens[i-1]) / atoi(tokens[i+1]);
            sprintf(tokens[i-1], "%d", result);
            for (int j = i; j < tokenCount - 2; j++) {
                strcpy(tokens[j], tokens[j+2]);
            }
            tokenCount -= 2;
        } else {
            i += 2;
        }
    }
    
    // Second pass: handle + and -
    int result = atoi(tokens[0]);
    i = 1;
    while (i < tokenCount) {
        if (strcmp(tokens[i], "+") == 0) {
            result += atoi(tokens[i+1]);
        } else if (strcmp(tokens[i], "-") == 0) {
            result -= atoi(tokens[i+1]);
        }
        i += 2;
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the string, each taking O(n) time

✓ Linear Growth

Space Complexity

O(n)

Storage for tokens and intermediate results

⚡ Linearithmic Space

285.0K Views

High Frequency

~25 min Avg. Time

4.2K 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

Two-Pass Evaluation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler