C++进阶之基于逆波兰表达式的计算器实现

用户11991900

发布于 2026-01-15 12:23:37

110

C++进阶之路系列将会与题目录系列一起继续我的C++学习，欢迎订阅专栏：C++系列
引言：我们进行计算机的使用时，使用的是中缀表达式。中缀表达式符合我们日常的逻辑计算。但对于计算机来说，想要识别中缀表达式的顺序却是件不容易的事情。在这里我们引出了逆波兰表达式（后缀表达式）来解决这一问题。

逆波兰表达式

相关题目：逆波兰表达式求值简要介绍：

逆波兰表达式是一种后缀表达式，由波兰数学家扬・武卡谢维奇于 1920 年提出，核心特点是运算符位于操作数之后（区别于日常使用的 “中缀表达式”，如a + b），无需括号即可明确表示运算优先级，广泛应用于计算机编译、计算器（如经典的 HP 计算器）等场景。

要实现计算器这个功能，第一步就是实现计算器能看懂的（后缀表达式）的计算。

计算规则

逆波兰表达式的计算依赖栈这种 “先进后出” 的数据结构，步骤简单且固定：从左到右扫描表达式的每个元素（操作数或运算符）；若遇到操作数，直接压入栈中；若遇到运算符，从栈中弹出最顶端的两个操作数（注意：先弹出的是 “右操作数”，后弹出的是 “左操作数”）；用该运算符对两个操作数进行计算，将结果重新压入栈中；扫描结束后，栈中剩余的唯一元素即为最终结果。

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for (size_t i = 0; i < tokens.size(); ++i) {
        const string& str = tokens[i];
        if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
            s.push(stoi(str));
        } else {
            int right = s.top();
            s.pop();
            int left = s.top();
            s.pop();
            switch (str[0]) {
            case '+':
                s.push(left + right);
                break;
            case '-':
                s.push(left - right);
                break;
            case '*':
                s.push(left * right);
                break;
            case '/':
                s.push(left / right);
                break;
            }
        }
    }
    return s.top();
}

功能：计算后缀表达式的值。
参数： tokens：后缀表达式，存储为字符串向量。
逻辑：使用一个栈 s 来存储操作数。
遍历 tokens：如果当前元素是数字，则将其转换为整数并压入栈。如果当前元素是运算符，则从栈中弹出两个操作数（右操作数和左操作数），根据运算符进行计算，并将结果压入栈。
最后，栈顶的值即为表达式的计算结果。

中缀转后缀

这里通过toRPN函数来实现这个功能。核心上来讲主要要注意对数字计算符以及括号的处理这里使用一个输出型参数vector< string >来接受后缀表达式。

map<char, int> _operatorPrecedence = {
    {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void toRPN(const string& s, size_t& i, vector<string>& v) {
    stack<char> st;
    while (i < s.size()) {
        if (isdigit(s[i])) {
            string num;
            while (i < s.size() && isdigit(s[i])) {
                num += s[i];
                ++i;
            }
            v.push_back(num);
        } else {
            if (s[i] == '(') {
                i++;
                toRPN(s, i, v);
            } else if (s[i] == ')') {
                i++;
                while (!st.empty()) {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
                return;
            } else {
                if (st.empty() || _operatorPrecedence[s[i]] >
                                          _operatorPrecedence[st.top()]) {
                    st.push(s[i]);
                    i++;
                } else {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
            }
        }
    }
    while (!st.empty()) {
        v.push_back(string(1, st.top()));
        st.pop();
    }
}

功能：将中缀表达式转换为后缀表达式（RPN，Reverse Polish Notation）。
参数： s：输入的字符串表达式。 i：当前处理的字符索引。 v：存储后缀表达式的向量。
逻辑：

遍历字符串 s，根据当前字符的类型进行不同处理：

数字：将连续的数字字符拼接成一个完整的数字字符串，并将其添加到结果向量 v 中。左括号 ‘(’：递归调用 toRPN，处理括号内的表达式。右括号 ‘)’：将栈中的运算符依次弹出并添加到结果向量 v 中，直到遇到左括号。
运算符：如果栈为空，或者当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符压入栈。否则，将栈顶运算符弹出并添加到结果向量 v 中，然后继续比较当前运算符和新的栈顶运算符。
最后，将栈中剩余的运算符依次弹出并添加到结果向量 v 中。

计算逻辑

这里需要对传入的中缀表达式进行处理，由于传入的字符串之中含有空格这一多余字符，我们首先就是要将空格去除。其次就是对于负数的处理，在我们对负数进行处理时，需要对‘-’进行分情况讨论，讨论其为负号，还是减号。

int calculate(string s) {
    std::string s1;
    s1.reserve(s.size());
    for (auto e : s) {
        if (e != ' ') {
            s1 += e;
        }
    }
    s.swap(s1);
    s1.clear();
    for (size_t i = 0; i < s.size(); ++i) {
        if (s[i]== '-' && (i == 0 || !isdigit(s[i - 1]) || s[i - 1] != ')')) {
            s1 += "0-";
        } else {
            s1 += s[i];
        }
    }

    size_t i = 0;
    vector<string> v;
    toRPN(s1, i, v);
    return evalRPN(v);
}

功能：计算输入字符串表达式的值。
逻辑：去除空格：将输入字符串 s 中的空格去除。处理负数：在表达式中，如果 - 出现在表达式的开头，或者前一个字符不是数字且不是右括号，则将其视为负数的开始，插入一个 0。转换为后缀表达式：调用 toRPN 方法将处理后的字符串转换为后缀表达式。计算后缀表达式的值：调用 evalRPN 方法计算后缀表达式的值并返回。