Cover image for Interview Classic 150 Questions P224 Basic Calculator

Interview Classic 150 Questions P224 Basic Calculator

(Updated: )
algorithm
, ,
Timeline

timeline

2025-12-18

init

stack

Title:

P224 Basic Calculator

https://leetcode.cn/problems/basic-calculator/description/?envType=study-plan-v2&envId=top-interview-150

First convert to prefix expression, then evaluate the prefix expression

  1. Need to first remove spaces from characters, and for negative sign (not minus, i.e., unary operator) insert 0 before it to make it a binary operator.

    • If ‘-’ is the first character, it is a unary operator i.e., negative sign, insert 0 before it

    • If ‘-’ is preceded by ‘(’, it is a unary operator i.e., negative sign, insert 0 before it

    • In other cases, ‘-’ is a binary operator i.e., minus sign

  2. Then convert to prefix expression, split operands and operators by spaces. First create a stack opStack to store symbols, record the return value asstring ret, traverse each character of the infix expression.

    • For numbers, keep adding to ret until the next character is not a digit, then add a space after ret to separate, indicating this is an operand, to facilitate subsequent evaluation of the prefix expression

    • For ‘(’, directly push onto opStack

    • For ‘)’, pop all binary operators (‘+’ or ‘-’ or ‘*’ or ‘/’) from opStack and add to ret, until the top is ‘(’, pop ‘(’ but do not add to ret

    • For binary operators (‘+’ or ‘-’ or ‘*’ or ‘/’)

      • If the top of the stack is also a binary operator, and the current binary operator has lower precedence than the top, then keep popping the top until this condition is no longer met, then push the current binary operator onto the stack
      • Otherwise, push the current binary operator onto the stack.

    • Finally, if opStack is not empty, pop the remaining elements one by one and add to ret

  3. Finally, evaluate the postfix expression. Note that it’s best to use long for evaluation, then convert to int at the end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <sstream>

using std::stack;
using std::string;
using std::vector;

class Solution {
    public:
        int getPrecedence(char op)
        {
                if (op == '+' || op == '-')
                        return 1;
                if (op == '*' || op == '/')
                        return 2;
                return 0;
        }

        // Helper: split the string by spaces
        vector<string> split(const string &s)
        {
                vector<string> tokens;
                std::istringstream iss(s);
                string token;
                while (iss >> token) {
                        tokens.push_back(token);
                }
                return tokens;
        }
        // Convert to prefix expression
        string conv_suffix_expr(string s)
        {
                string ret;
                stack<char> opStack;
                char ch;
                int i = 0, n = s.size();

                while (i < n) {
                        ch = s[i];

                        // Handle multi-digit numbers
                        if (std::isdigit(ch)) {
                                while (i < n && std::isdigit(s[i])) {
                                        ret += s[i];
                                        i++;
                                }
                                ret += " "; // Add space separation
                                i--; // Will i++ later
                        } else if (ch == '(') { // Left parenthesis
                                opStack.push(ch);
                        } else if (ch == ')') { // Right parenthesis
                                while (!opStack.empty() && opStack.top() != '(') {
                                        ret += opStack.top();
                                        ret += " ";
                                        opStack.pop();
                                }
                                if (!opStack.empty())
                                        opStack.pop(); // pop '('
                        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { // operator
                                while (!opStack.empty() &&
                                       getPrecedence(opStack.top()) > 0 && //top of stack is also a binary operator
                                       getPrecedence(opStack.top()) >= getPrecedence(ch)) { // the precedence of the operator corresponding to current ch is less than that of the operator at the top of the stack
                                        ret += opStack.top();
                                        ret += " ";
                                        opStack.pop();
                                }
                                opStack.push(ch);
                        }

                        i++; // advance one position for normal characters (operators/parentheses)
                }

                // pop remaining operators
                while (!opStack.empty()) {
                        ret += opStack.top();
                        ret += " ";
                        opStack.pop();
                }

                return ret;
        }
        // evaluation of prefix expression
        int suffix_expr_cal(string &postfix)
        {
                vector<string> tokens = split(postfix);
                stack<long> st;
                long a, b;

                for (const string &token : tokens) {
                        if (token == "+" || token == "-" || token == "*" || token == "/") {
                                b = st.top();
                                st.pop();
                                a = st.top();
                                st.pop();
                                if (token == "+")
                                        st.push(a + b);
                                else if (token == "-")
                                        st.push(a - b);
                                else if (token == "*")
                                        st.push(a * b);
                                else if (token == "/")
                                        st.push(a / b);
                        } else {
                                st.push(std::stol(token));
                        }
                }

                return (int)st.top();
        }
        string handleUnaryMinus(const string &s)
        {
                string clean;
                for (char c : s) {
                        if (c != ' ')
                                clean += c;
                }

                string result;
                int n = clean.size();

                for (int i = 0; i < n; ++i) {
                        char c = clean[i];
                        if (c == '-') {
                                // determine if it is a unary minus:
                                // case 1: at the beginning
                                // case 2: previous character is '(' or other operators (+, -, *, /)
                                if (i == 0) {
                                        result += "0-";
                                } else {
                                        char prev = clean[i - 1];
                                        if (prev == '(') {
                                                result += "0-";
                                        } else {
                                                result += '-';
                                        }
                                }
                        } else {
                                result += c;
                        }
                }
                return result;
        }

        int calculate(string s)
        {
                s = handleUnaryMinus(s); // insert 0 before '-'
                string postfix = conv_suffix_expr(s);
                return suffix_expr_cal(postfix);
        }
};

only addition and subtraction

Since the string contains only addition and subtraction operators besides numbers and parentheses, if all parentheses in the expression are expanded, the numbers themselves do not change in the new expression, only the sign before each number changes. Parentheses cannot be ignored because although ‘+’ and ‘-’ have the same precedence, parentheses change the precedence.
The main change is that there is no precedence judgment for binary operators. That is, the original rule ‘if the top of the stack is also a binary operator and the precedence of the current binary operator is less than that of the top, then keep popping the top until this condition is no longer satisfied, and finally push the current binary operator onto the stack’ becomes ‘if the top of the stack is a binary operator, then keep popping the top until this condition is no longer satisfied, and finally push the current binary operator onto the stack’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
string conv_suffix_expr(string s) {
    string ret;
    stack<char> opStack;
    int i = 0, n = s.size();

    while (i < n) {
        char ch = s[i];

        if (std::isdigit(ch)) {
            while (i < n && std::isdigit(s[i])) {
                ret += s[i];
                i++;
            }
            ret += " ";
            i--;
        }eles if (ch == '(') {
            opStack.push(ch);
        }else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                ret += opStack.top();
                ret += " ";
                opStack.pop();
            }
            if (!opStack.empty()) opStack.pop(); // pop '('
        }else if (ch == '+' || ch == '-') {
            // pop all binary operators whose top of stack is not '('
            while (!opStack.empty() &&
                   opStack.top() != '(' ) {
                ret += opStack.top();
                ret += " ";
                opStack.pop();
            }
            opStack.push(ch);
        }

        i++;
    }

    while (!opStack.empty()) {
        ret += opStack.top();
        ret += " ";
        opStack.pop();
    }

    return ret;
}