LeetCode 224 – Basic Calculator: Problem Description, Analysis, and Reference Solution

In many interview processes there is an unwritten rule: if the interviewer is satisfied they may give an easy or scoring question, otherwise they may present a hard problem that can lead to rejection; one candidate failed a hard "Rectangle Area" question and was turned down.

Continuing the algorithm series, the article presents a challenging problem titled "Basic Calculator".

1. Problem Description

Given a string expression s , implement a basic calculator that evaluates and returns its integer value.

Examples

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

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

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Hints

1 <= s.length <= 3 * 10^5

The string consists of digits, '+', '-', '(', ')', and spaces.

s represents a valid arithmetic expression.

2. Analysis

Algorithm Points

Use a stack to handle the order of operations introduced by parentheses.

Perform string traversal and character conversion.

Apply calculation logic based on the precedence dictated by parentheses.

Algorithm Idea

Maintain a stack to store intermediate results and signs outside parentheses.

Traverse the string from left to right, processing each character: If the character is a digit, convert it to an integer (handling multi‑digit numbers) and add it to the result with the current sign. If the character is '+' or '-', update the current sign accordingly. If the character is '(', push the current result and sign onto the stack, then reset result and sign. If the character is ')', pop the sign and previous result from the stack and combine them with the current result.

After the full traversal, the top of the stack holds the final calculation result.

3. Reference Code

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution {
    public int calculate(String s) {
        // 使用栈来储存字符串表达式中的数字
        Stack
stack = new Stack
();
        // 为了方便计算，所有的操作都视为加法操作
        // 那么原先的减法操作就相当于是加一个负数
        // 默认都是正数
        int sign = 1;
        // 保存计算的结果
        int res = 0;
        // 获取字符串的长度，然后获取里面的每个字符
        int length = s.length();
        // 获取字符串里面的每个字符
        for (int i = 0; i < length; i++) {
            // 获取此时的字符
            char ch = s.charAt(i);
            // 如果当前字符是数字的话
            if (Character.isDigit(ch)) {
                // 那么可以通过 - '0' 这个操作把字符转换为整数
                // 相当于转换成了 ascii 码进行的数字运算
                int value = ch - '0';
                // 去查看当前字符的后一位是否存在
                // 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1))) {
                    // i 向后移动，直到遇到非数字为止
                    i++;
                    // i 每向后移动一位，当前的值就需要乘以 10
                    // 比如 s 为 "123+456"
                    // 此时 i = 0，那么 value 为 1
                    // i = 1，那么 value 为 1 * 10 + 2 = 12
                    // i = 2，那么 value 为 12 * 10 + 3 = 123
                    value = value * 10 + s.charAt(i) - '0';
                }
                // 那么把获取到的数累加到结果 res 上
                res = res + sign * value;
                // 如果是 '+'
            } else if (ch == '+') {
                // 那么说明直接加一个正数
                sign = 1;
                // 如果是 '-'
            } else if (ch == '-') {
                // 那么说明加一个负数
                sign = -1;
                // 如果是 '('
            } else if (ch == '(') {
                // 1、先把 ( 之前的结果存放到栈中
                stack.push(res);
                // 2、重新初始化 res 为 0
                res = 0;
                // 3、把 ( 左边的操作符号存放到栈中
                stack.push(sign);
                // 4、默认都是正数
                sign = 1;
                // 如果是 ')'
            } else if (ch == ')') {
                // 先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
                int formerSign = stack.peek();
                stack.pop();
                // 再获取栈顶元素，即左括号结果
                int formerRes = stack.peek();
                stack.pop();
                // 结果 = 左括号外的结果 + (符号 * 括号内的结果)
                res = formerRes + formerSign * res;
            }
        }
        // 返回计算好的结果
        return res;
    }
}

Related articles for further reading:

These Java Tips You Should Know

Differences Between Docker and Traditional Virtual Machines

How Redis Implements Distributed Locks