Classic Interview 150 Questions P224 Basic Calculator

---

Timeline

Timeline

2025-12-18

init

Stack

---

Problem:

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 the characters, and for the negative sign (not minus sign, i.e., unary operator), insert 0 before it to turn it into a binary operator.

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

   • If the character before ‘-’ is ‘(’, 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 an operator stack opStack, let the return value bestring ret, traverse each character of the infix expression.

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

   • For ‘(’, directly push it onto opStack.

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

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

     • If the top element of the stack is also a binary operator, and the priority of the current binary operator is less than the priority of the top of the stack, then keep popping the top until this condition is no longer satisfied, and finally push the current binary operator onto the stack.
     • In other cases, push the current binary operator onto the stack.

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

3. Finally evaluate the postfix expression. Note that it is best to use long for evaluation, and finally convert to int.

#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 a space for separation.
                                i--; // i++ will be done 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 && //The top of the stack is also a binary operator
                                       getPrecedence(opStack.top()) >= getPrecedence(ch)) { // The precedence of the operator corresponding to the current ch is lower than the precedence of the operator at the top of the stack
                                        ret += opStack.top();
                                        ret += " ";
                                        opStack.pop();
                                }
                                opStack.push(ch);
                        }

                        i++; // Advance one position for a normal character (operator/parenthesis)
                }

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

                return ret;
        }
        // Prefix expression evaluation
        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 whether it is a unary minus sign:
                                // Case 1: at the beginning
                                // Case 2: the previous character is '(' or another operator (+, -, *, /)
                                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 two operators, plus and minus, besides numbers and parentheses, if all parentheses in the expression are expanded, the numbers themselves in the resulting new expression do not change; only the sign before each number changes. Parentheses cannot be ignored, because although “+” and “-” have the same precedence, parentheses can change the precedence.
The main change is that the precedence comparison for binary operators is removed. 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 lower than the precedence of the top of the stack, 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.”

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 while the top of the 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;
}