每日一题：使用栈实现逆波兰表达式求值

使用栈实现逆波兰表达式求值（C++详解）

---

基础知识参考文章：数据结构：栈和队列(Stack & Queue)基本概念与应用

---

本文主要介绍了如何使用使用栈实现逆波兰表达式求值，并对程序结构和运行顺序逻辑进行了介绍。

文章目录

• 使用栈实现逆波兰表达式求值（C++详解）
• • @[TOC](文章目录)
  • 一、问题概述
  • 二、算法原理
  • • 2.1 逆波兰表达式特点
    • 2.2 栈的应用原理
  • 三、C++实现
  • • 3.1 完整代码
    • 3.2 关键代码解析
  • 四、算法分析
  • • 4.1 时间复杂度
    • 4.2 空间复杂度
  • 五、边界情况处理
  • 六、测试用例
  • 七、应用场景
  • 八、总结
  • 二编：更加清晰了解程序结构
  • • 1. 程序执行顺序与操作流程
    • 2. 数字与符号的辨别机制
    • 3. 数据存入`nums`栈的时机与方式
    • 4 辨别数字和运算符号
    • 语法解析
    • 等效替代方案
    • 典型应用场景
  • 更适合初学者的一种写法
  • 使用map进行求值，很高级

一、问题概述

逆波兰表达式（Reverse Polish Notation，RPN），又称后缀表达式，是一种不需要括号就能明确运算顺序的数学表达式表示方法。给定一个包含整数和运算符（+、-、*、/）的逆波兰表达式，要求计算该表达式的值。

示例：

• 输入：["2","1","+","3","*"]
  输出：9（对应中缀表达式：(2 + 1) * 3）
• 输入：["4","13","5","/","+"]
  输出：6（对应中缀表达式：4 + (13 / 5)）

特殊要求：

1. 除法结果向零取整（截断小数部分）
2. 表达式保证合法
3. 时间复杂度O(n)，空间复杂度O(n)

二、算法原理

2.1 逆波兰表达式特点

逆波兰表达式是一种将运算符放在操作数之后的表示方法，与常规的中缀表达式相比具有以下显著特点：

1. 操作数在前，运算符在后

   • 中缀表达式：(3 + 4) × 5
   • 逆波兰式：3 4 + 5 ×

2. 无括号设计

   • 中缀表达式需要括号来明确优先级：3 × (4 + 5)
   • 逆波兰式通过运算符位置表达优先级：3 4 5 + ×

3. 明确的计算顺序

   • 计算顺序完全由运算符位置决定
   • 示例：5 1 2 + 4 × + 3 -

     计算步骤：
     1. 1 2 + → 3
     2. 3 4 × → 12 
     3. 5 12 + → 17
     4. 17 3 - → 14
     

2.2 栈的应用原理

栈的"后进先出"（LIFO）特性与逆波兰表达式的计算顺序完美契合：

计算过程示例：["4", "13", "5", "/", "+"]

步骤	当前token	栈状态	操作说明
1	“4”	[4]	数字直接入栈
2	“13”	[4, 13]	数字直接入栈
3	“5”	[4, 13, 5]	数字直接入栈
4	“/”	[4, 2]	弹出5和13，计算13/5=2（向零取整）
5	“+”	[6]	弹出2和4，计算4+2=6

关键优势：

1. 自动处理优先级：运算符位置天然包含优先级信息
   • 例如：3 4 × 5 +等价于(3×4)+5
2. 简化计算流程：无需维护运算符优先级栈
3. 高效的内存使用：只需一个操作数栈

对比中缀表达式计算：

• 中缀计算需要两个栈（操作数栈和运算符栈）
• 需要处理括号和优先级判断
• 计算逻辑更复杂，代码量通常多2-3倍

这种基于栈的计算方法在编译器设计、计算器实现等领域有着广泛应用，是计算机处理数学表达式的经典范式。

三、C++实现

3.1 完整代码

#include <vector>
#include <stack>
#include <string>
#include <stdexcept>
#include <cctype>using namespace std;class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> nums; // 操作数栈for (const auto& token : tokens) {if (isOperator(token)) {// 检查栈大小if (nums.size() < 2) {throw invalid_argument("Invalid RPN expression");}// 获取操作数（注意顺序）int b = nums.top(); nums.pop();int a = nums.top(); nums.pop();// 执行运算int result = 0;switch (token[0]) {case '+': result = a + b; break;case '-': result = a - b; break;case '*': result = a * b; break;case '/': if (b == 0) throw runtime_error("Division by zero");result = a / b; break;}nums.push(result);}else {// 处理数字（包括负数）nums.push(stoi(token));}}if (nums.size() != 1) {throw invalid_argument("Invalid RPN expression");}return nums.top();}private:bool isOperator(const string& s) {return s.size() == 1 && string("+-*/").find(s) != string::npos;}
};

3.2 关键代码解析

1. 栈的初始化

stack<int> nums;

使用C++ STL的stack容器存储操作数

2. 运算符判断

bool isOperator(const string& s) {return s.size() == 1 && string("+-*/").find(s) != string::npos;
}

判断字符串是否为四则运算符

3. 数字转换

nums.push(stoi(token));

使用stoi自动处理正负数转换

4. 除法处理

case '/': if (b == 0) throw runtime_error("Division by zero");result = a / b; break;

包含除零检查，使用整数除法实现向零取整

四、算法分析

4.1 时间复杂度

• O(n)：只需一次遍历所有token
• 每个token处理都是O(1)操作

4.2 空间复杂度

• O(n)：最坏情况下需要存储所有操作数
• 对于n个token，操作数最多⌈n/2⌉+1个

五、边界情况处理

1. 非法表达式检测

if (nums.size() < 2) {throw invalid_argument("Invalid RPN expression");
}

确保运算符有足够操作数

2. 最终结果验证

if (nums.size() != 1) {throw invalid_argument("Invalid RPN expression");
}

确保表达式完整计算

3. 除零检查

if (b == 0) throw runtime_error("Division by zero");

避免除零错误

六、测试用例

void test() {Solution sol;vector<string> test1 = {"2","1","+","3","*"};cout << sol.evalRPN(test1) << endl; // 输出9vector<string> test2 = {"4","13","5","/","+"};cout << sol.evalRPN(test2) << endl; // 输出6vector<string> test3 = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};cout << sol.evalRPN(test3) << endl; // 输出22
}

七、应用场景

1. 科学计算器实现
2. 编译器语法分析
3. 数据库查询优化
4. 数学表达式解析引擎

八、总结

本文详细介绍了使用C++和栈数据结构实现逆波兰表达式求值的完整解决方案。该算法具有以下特点：

1. 时间复杂度O(n)，空间复杂度O(n)
2. 包含完善的错误处理机制
3. 代码简洁高效，充分利用STL特性
4. 可扩展性强，易于添加新运算符

通过这个实现，我们可以深入理解栈数据结构的应用场景和使用技巧。

---

二编：更加清晰了解程序结构

1. 程序执行顺序与操作流程

代码执行路径：

for (const auto& token : tokens) {  // 顺序遍历每个tokenif (isOperator(token)) {       // 分支1：处理运算符// 弹出操作数 → 计算 → 结果入栈} else {                      // 分支2：处理数字nums.push(stoi(token));    // 数字转换后立即入栈}
}

可视化流程（以 ["4","13","5","/","+"] 为例）：

步骤	Token	动作类型	栈状态变化	关键操作说明
1	“4”	数字处理	[] → [4]	stoi(“4”)→4 入栈
2	“13”	数字处理	[4] → [4,13]	stoi(“13”)→13 入栈
3	“5”	数字处理	[4,13] → [4,13,5]	stoi(“5”)→5 入栈
4	“/”	运算符处理	[4,13,5] → [4,2]	弹出5,13 → 计算13/5=2 入栈
5	“+”	运算符处理	[4,2] → [6]	弹出2,4 → 计算4+2=6 入栈

---

2. 数字与符号的辨别机制

辨别逻辑代码：

bool isOperator(const string& s) {// 长度=1且在"+-*/"中即为运算符return s.size() == 1 && string("+-*/").find(s) != string::npos;
}

决策过程：

1. 数字特征：
   • 长度可能>1（如"-123"）
   • 包含数字字符（通过stoi()验证）
2. 符号特征：
   • 严格长度=1
   • 字符属于{+,-,*,/}

示例辨别：

Token	isOperator结果	处理方式
“42”	false	stoi(“42”)→42入栈
“-5”	false	stoi(“-5”)→-5入栈
“*”	true	触发运算逻辑

---

3. 数据存入nums栈的时机与方式

存入逻辑代码：

nums.push(stoi(token));  // 在else分支直接存入

关键规则：

1. 立即存入：数字在识别后不经任何计算直接入栈
2. 延迟存入：运算符处理后的结果才会入栈
3. 类型转换：

   stoi("-123")  // 自动处理负号和多位数
   → 转换为int型-123
   → 存入栈
   

内存变化示意图：

步骤1: "4" → nums栈底[4]
步骤2: "13" → nums栈底[4] → [13]
步骤3: "5" → nums栈底[4] → [13] → [5]（栈顶）
步骤4: "/"运算 → nums变为[4] → [2]（新栈顶）
步骤5: "+"运算 → nums最终[6]

4 辨别数字和运算符号

string("+-*/").find(s) != string::npos 是C++中用于判断字符串是否包含特定字符的常用方法。下面详细解释它的工作原理：

语法解析

string("+-*/").find(s) != string::npos

1. string("+-*/")

   • 创建一个临时字符串对象，内容为"+-*/"（四个运算符字符）

2. .find(s)

   • 在该字符串中查找子串s
   • 返回值为size_t类型（无符号整数），表示s首次出现的位置索引
   • 如果未找到，返回特殊常量string::npos

3. != string::npos

   • 判断查找结果是否有效（即s是否存在于运算符字符串中）

具体行为

输入s	.find(s)返回值	比较结果	含义
"+"	0	0 != npos → true	是运算符
"*"	2	2 != npos → true	是运算符
"1"	npos	npos != npos → false	不是运算符
"++"	npos	npos != npos → false	不是运算符（长度已过滤）

1. 高效性：

   • 只需一次函数调用完成查找
   • 比多个if(s=="+"||s=="-"...)更简洁

2. 可扩展性：

   • 如需增加运算符（如%），只需修改字符串内容：

     string("+-*/%")...
     

3. 安全性：

   • 与s.size() == 1配合可严格限定单字符运算符

等效替代方案

// 方案1：逐个字符比较
if (s == "+" || s == "-" || s == "*" || s == "/")// 方案2：C风格函数
if (strchr("+-*/", s[0]) && s.size() == 1)

典型应用场景

bool isOperator(const string& s) {// 必须同时满足：// 1. 长度=1（排除数字和无效输入）// 2. 是四个运算符之一return s.size() == 1 && string("+-*/").find(s) != string::npos;
}

更适合初学者的一种写法

class Solution {
public:/*** * @param tokens string字符串vector * @return int整型*/int evalRPN(vector<string>& tokens) {stack<int> num; // 操作数栈// write code hereint length = tokens.size();for(int i=0; i< length;i++){if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {int b = num.top(); num.pop();int a = num.top(); num.pop();if (tokens[i] == "+") num.push(a + b);else if (tokens[i] == "-") num.push(a - b);else if (tokens[i] == "*") num.push(a * b);else if (tokens[i] == "/") num.push(a / b);} else {num.push(stoi(tokens[i]));}}return num.top();}};

使用map进行求值，很高级

#include <vector>
#include <stack>
#include <string>
#include <functional>
#include <unordered_map>
#include <variant>
#include <stdexcept>using namespace std;class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> operands;const unordered_map<string, function<int(int, int)>> operations{{"+", [](int a, int b) { return a + b; }},{"-", [](int a, int b) { return a - b; }},{"*", [](int a, int b) { return a * b; }},{"/", [](int a, int b) { if (b == 0) throw runtime_error("Division by zero");return a / b; }}};for (const auto& token : tokens) {if (operations.count(token)) {if (operands.size() < 2) throw invalid_argument("Invalid RPN expression");int b = operands.top(); operands.pop();int a = operands.top(); operands.pop();operands.push(operations.at(token)(a, b));} else {try {operands.push(stoi(token));} catch (...) {throw invalid_argument("Invalid token: " + token);}}}if (operands.size() != 1) throw invalid_argument("Invalid RPN expression");return operands.top();}
};