Basic Calculator III

Published at23 Jul 2026

Stack Hard 0 views

Like0

Evaluate an arithmetic expression with integers, operators +, -, *, /, and parentheses ( ). The expression is always valid. Integer division truncates toward zero.

This extends Basic Calculator II by adding nested parentheses. Two stacks handle this: one for operands, one for operators. When an operator arrives, while the top of the operator stack has equal or higher precedence, pop and compute. Parentheses mark expression boundaries: push ( to operator stack, and when ) is encountered, compute until matching (. This is the shunting-yard algorithm adapted for evaluation.

The two-stack approach (one for operands, one for operators) handles the full arithmetic expression evaluation. Numbers are pushed onto the operand stack. Operators are pushed onto the operator stack, but only after all operators with higher or equal precedence have been popped and evaluated. Parentheses create a sub-expression boundary: when an opening parenthesis is encountered, it is pushed as a marker. When a closing parenthesis is encountered, all operators until the matching opening parenthesis are evaluated.

This is the standard shunting-yard algorithm adapted for direct evaluation. Understanding this algorithm is essential for building expression evaluators and interpreters. The same technique applies to evaluating reverse Polish notation and Boolean expressions.

Integer division must truncate toward zero, which affects how negative results are computed. The expression is guaranteed to be valid and will not contain division by zero. Operators are evaluated with standard precedence rules: multiplication and division before addition and subtraction. Parentheses override precedence. This problem is commonly asked in senior-level interviews as it tests understanding of expression parsing, precedence, and stack-based evaluation.

Negative numbers are handled by the subtraction operator: when a minus sign is encountered, the next number is subtracted rather than added. Consecutive operators like 1--2 are not allowed in this problem. The input is always well-formed.

Example Input & Output

Example 1

Input

1+2*3

Output

Explanation

2*3=6, 1+6=7.

Example 2

Input

(1+2)*3

Output

Explanation

Parentheses first.

Example 3

Input

(2+3)*(4+5)

Output

Explanation

Nested parentheses.

Algorithm Flow

Recommendation Algorithm Flow for Basic Calculator III

Solution Approach

Two stacks: nums and ops. Parse numbers. Handle operators with precedence. Parentheses create sub-expressions.

function solution(s) {
  var nums = [], ops = [], num = 0, sign = 1, i = 0;
  while (i < s.length) {
    var ch = s[i];
    if (ch >= "0" && ch <= "9") {
      num = 0;
      while (i < s.length && s[i] >= "0" && s[i] <= "9") { num = num*10 + +s[i]; i++; }
      nums.push(sign * num); sign = 1; continue;
    } else if (ch === "(") { ops.push(ch); }
    else if (ch === ")") {
      while (ops.length && ops[ops.length-1] !== "(") calc(nums, ops);
      ops.pop();
    } else if ("+-*/".indexOf(ch) >= 0) {
      while (ops.length && prec(ops[ops.length-1]) >= prec(ch)) calc(nums, ops);
      ops.push(ch);
    }
    i++;
  }
  while (ops.length) calc(nums, ops);
  return nums[0];
  function calc(n, o) {
    var b = n.pop(), a = n.pop(), op = o.pop();
    n.push(op === "+" ? a+b : op === "-" ? a-b : op === "*" ? a*b : Math.trunc(a/b));
  }
  function prec(op) { return op === "*" || op === "/" ? 2 : 1; }
}

Time O(n), Space O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int solution(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int num = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') { num = num * 10 + (s.charAt(i) - '0'); i++; }
                nums.push(num); continue;
            } else if (ch == '(') { ops.push(ch); }
            else if (ch == ')') {
                while (!ops.isEmpty() && ops.peek() != '(') calc(nums, ops);
                ops.pop();
            } else if ("+-*/".indexOf(ch) >= 0) {
                while (!ops.isEmpty() && prec(ops.peek()) >= prec(ch)) calc(nums, ops);
                ops.push(ch);
            }
            i++;
        }
        while (!ops.isEmpty()) calc(nums, ops);
        return nums.pop();
    }
    void calc(Stack<Integer> nums, Stack<Character> ops) {
        int b = nums.pop(), a = nums.pop();
        char op = ops.pop();
        if (op == '+') nums.push(a + b); else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b); else nums.push(a / b);
    }
    int prec(char op) { return op == '*' || op == '/' ? 2 : op == '(' ? 0 : 1; }
}

javascript

function solution(s) {
  var nums = [], ops = [], i = 0;
      function calc() {
    var b = nums.pop(), a = nums.pop(), op = ops.pop();
    if (op === '+') nums.push(a + b); else if (op === '-') nums.push(a - b);
    else if (op === '*') nums.push(a * b); else nums.push(Math.trunc(a / b));
  }
  function prec(op) { return op === '*' || op === '/' ? 2 : op === '(' ? 0 : 1; }
  while (i < s.length) {
    var ch = s[i];
    if (ch >= '0' && ch <= '9') {
      var num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') { num = num * 10 + Number(s[i]); i++; }
      nums.push(num); continue;
    } else if (ch === '(') { ops.push(ch); }
    else if (ch === ')') {
      while (ops.length && ops[ops.length-1] !== '(') calc();
      ops.pop();
    } else if ('+-*/'.indexOf(ch) >= 0) {
      while (ops.length && prec(ops[ops.length-1]) >= prec(ch)) calc();
      ops.push(ch);
    }
    i++;
  }
  while (ops.length) calc();
  return nums[0];
}

php

<?php
function solution($s) {
    $nums = []; $ops = []; $i = 0;
    while ($i < strlen($s)) {
        $ch = $s[$i];
        if ($ch >= '0' && $ch <= '9') {
            $num = 0;
            while ($i < strlen($s) && $s[$i] >= '0' && $s[$i] <= '9') { $num = $num * 10 + intval($s[$i]); $i++; }
            array_push($nums, $num); continue;
        } elseif ($ch == '(') { array_push($ops, $ch); }
        elseif ($ch == ')') {
            while (!empty($ops) && end($ops) != '(') {
                $b = array_pop($nums); $a = array_pop($nums); $op = array_pop($ops);
                if ($op == '+') array_push($nums, $a + $b); elseif ($op == '-') array_push($nums, $a - $b);
                elseif ($op == '*') array_push($nums, $a * $b); else array_push($nums, intdiv($a, $b));
            }
            array_pop($ops);
        } elseif (in_array($ch, ['+','-','*','/'])) {
            $p = ($ch=='*'||$ch=='/')?2:($ch=='('?0:1);
            while (!empty($ops) && ((end($ops)=='*'||end($ops)=='/')?2:(end($ops)=='('?0:1))>=$p) {
                $b = array_pop($nums); $a = array_pop($nums); $op = array_pop($ops);
                if ($op == '+') array_push($nums, $a + $b); elseif ($op == '-') array_push($nums, $a - $b);
                elseif ($op == '*') array_push($nums, $a * $b); else array_push($nums, intdiv($a, $b));
            }
            array_push($ops, $ch);
        }
        $i++;
    }
    while (!empty($ops)) {
        $b = array_pop($nums); $a = array_pop($nums); $op = array_pop($ops);
        if ($op == '+') array_push($nums, $a + $b); elseif ($op == '-') array_push($nums, $a - $b);
        elseif ($op == '*') array_push($nums, $a * $b); else array_push($nums, intdiv($a, $b));
    }
    return $nums[0];
}

python

def solution(s):
    nums, ops = [], []
    i, n = 0, len(s)
    def calc():
        b = nums.pop(); a = nums.pop(); op = ops.pop()
        if op == '+': nums.append(a + b)
        elif op == '-': nums.append(a - b)
        elif op == '*': nums.append(a * b)
        else: nums.append(int(a / b))
    def prec(op): return 2 if op in '*/' else 0 if op == '(' else 1
    while i < n:
        ch = s[i]
        if ch.isdigit():
            num = 0
            while i < n and s[i].isdigit():
                num = num * 10 + int(s[i]); i += 1
            nums.append(num)
            continue
        elif ch == '(': ops.append(ch)
        elif ch == ')':
            while ops and ops[-1] != '(': calc()
            ops.pop()
        elif ch in '+-*/':
            while ops and prec(ops[-1]) >= prec(ch): calc()
            ops.append(ch)
        i += 1
    while ops: calc()
    return nums[0]

rust

fn solution(s: &str) -> i32 {
    let mut nums: Vec<i32> = Vec::new();
    let mut ops: Vec<char> = Vec::new();
    let chars: Vec<char> = s.chars().collect();
    let mut i = 0;
    while i < chars.len() {
        let ch = chars[i];
        if ch.is_digit(10) {
            let mut num = 0;
            while i < chars.len() && chars[i].is_digit(10) { num = num * 10 + (chars[i] as i32 - 48); i += 1; }
            nums.push(num); continue;
        } else if ch == '(' { ops.push(ch); }
        else if ch == ')' {
            while !ops.is_empty() && *ops.last().unwrap() != '(' { calc(&mut nums, &mut ops); }
            ops.pop();
        } else if "+-*/".contains(ch) {
            while !ops.is_empty() && prec(*ops.last().unwrap()) >= prec(ch) { calc(&mut nums, &mut ops); }
            ops.push(ch);
        }
        i += 1;
    }
    while !ops.is_empty() { calc(&mut nums, &mut ops); }
    nums[0]
}
fn prec(op: char) -> i32 { if op == '*' || op == '/' { 2 } else if op == '(' { 0 } else { 1 } }
fn calc(nums: &mut Vec<i32>, ops: &mut Vec<char>) {
    let b = nums.pop().unwrap(); let a = nums.pop().unwrap(); let op = ops.pop().unwrap();
    match op { '+' => nums.push(a + b), '-' => nums.push(a - b), '*' => nums.push(a * b), _ => nums.push(a / b) }
}

typescript

function solution(s: string): number {
  var nums: number[] = [], ops: string[] = [], i = 0;
  function calc(): void {
    var b = nums.pop() as number, a = nums.pop() as number, op = ops.pop() as string;
    if (op === '+') nums.push(a + b); else if (op === '-') nums.push(a - b);
    else if (op === '*') nums.push(a * b); else nums.push(~~(a / b));
  }
  function prec(op: string): number { return op === '*' || op === '/' ? 2 : op === '(' ? 0 : 1; }
  while (i < s.length) {
    var ch = s[i];
    if (ch >= '0' && ch <= '9') {
      var num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') { num = num * 10 + Number(s[i]); i++; }
      nums.push(num); continue;
    } else if (ch === '(') { ops.push(ch); }
    else if (ch === ')') {
      while (ops.length && ops[ops.length-1] !== '(') calc();
      ops.pop();
    } else if ('+-*/'.indexOf(ch) >= 0) {
      while (ops.length && prec(ops[ops.length-1] as string) >= prec(ch)) calc();
      ops.push(ch);
    }
    i++;
  }
  while (ops.length) calc();
  return nums[0];
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Basic Calculator III

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Maximum Nesting Depth

Simplify Path

Final Prices With Discount

Clear Digits

Crawler Log Folder

Build Array With Stack Operations

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.