C++实现字符串的逆波兰表达式求值逻辑 _ 栈结构与算术解析算法【详解】

雨涛大大_2569

雨涛大大_2569

2026-04-28

514人浏览

原创

正确弹出顺序为先取右操作数再取左操作数,即 int right = st.top(); st.pop(); int left = st.top(); st.pop();,否则减除结果错误;运算符须用完整字符串匹配,负数由 stoi() 安全处理;必须检查栈大小和除零。

c++实现字符串的逆波兰表达式求值逻辑 _ 栈结构与算术解析算法【详解】

怎么用 std::stack 正确弹出左右操作数

顺序反了,减法和除法结果就全错。栈是后进先出,所以对 token 序列 ["4","13","5","+","/"],遇到 "/" 时栈内是 [4, 18](13+5 的结果压在 4 上面)。必须先 st.top(); st.pop(); 拿到 18(右操作数),再取一次拿到 4(左操作数),最后算 4 / 18。如果颠倒顺序,就会变成 18 / 4 == 4,完全错误。

实操建议:

  • 每次运算前固定写两行:int right = st.top(); st.pop(); int left = st.top(); st.pop();
  • 别用 st.pop(); st.top() 这种组合——pop() 不返回值,第二次 top() 就读错了
  • 变量名强制用 left/right,不用 a/b,避免脑内混淆

为什么 stoi() 能直接处理负数但不能乱用

stoi("-123") 没问题,但 stoi("-") 会抛 std::invalid_argument。关键不在函数本身,而在你有没有提前把运算符 "-" 和负数字符串 "-123" 区分开。

常见错误现象:把 token 逐字符判断,看到第一个字符是 '-' 就当运算符,结果把 "-5" 拆成 "-" 和 "5" 两次入栈,后续计算彻底崩坏。

实操建议:

  • 只用 s == "+" || s == "-" || s == "*" || s == "/" 判断运算符,不看首字符
  • 所有不匹配的 token 统一走 stoi(s),包括 "-42"、"1000"、"0"
  • 外层加 try-catch 捕获 std::invalid_argument,用于拦截 "abc" 这类非法输入

除零和栈空检查不是可选项,是必做动作

题目说“表达式中不含除零运算”,但那是 OJ 数据的保证,不是你代码的免责条款。真实场景下,用户输错一个 ["5","0","/"],你的程序直接 st.top() 崩溃,或者 5 / 0 触发未定义行为。

C++14
C++14

C++14 对 C++11 的修正与增强版本,适合旧系统维护和较老工具链兼容。

下载

性能影响几乎为零,但漏掉检查会让整个求值逻辑不可靠。

实操建议:

  • 每次执行运算前,先检查 if (st.size() ,不够两个数就 throw 或 return 错误码
  • 遇到 "/" 时,拿到 right 后立刻 if (right == 0) 判断,别等 left / right 执行完再检查
  • 别依赖“题目保证合法”跳过这些——本地调试时随便改个 token 就能复现段错误

std::stack 足够快,别自己造轮子

有人担心 std::stack 底层用 std::deque 有额外开销,其实对几百个 token 的表达式,压栈弹栈几十次的耗时远低于字符串分割和 stoi 解析。真瓶颈从来不在栈本身。

实操建议:

  • 直接用 std::stack,别手写数组栈或封装 vector 模拟
  • 如果硬要换容器,用 std::stack> 即可,别自己实现 push/pop
  • reserve 没意义——逆波兰长度未知,动态增长更安全;且栈深度通常远小于 token 总数

最易被忽略的是弹栈顺序和错误检查的耦合:你以为只检查除零就够了,但 st.size() 在除法前没拦住,right 可能根本没取到,后面判零就无从谈起。这两件事得写在一起,不能拆开。

C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!

相关专题

更多
c++和c语言的区别有哪些
c++和c语言的区别有哪些

c++和c语言的区别:1、面向对象编程(OOP)支持不同;2、新增特性不同;3、标准库不同;4、编译方式不同;5、命名空间不同等等。想了解更多c++的相关内容,可以阅读本专题下面的文章。

2024.03.14

2288

9

c++和python学习顺序推荐
c++和python学习顺序推荐

一般建议先学习C++,再学习Python,因为这样可以逐步从较为底层的编程语言向更高级的语言过渡。想了解更多python的相关内容,可以阅读本专题下面的文章。

2024.03.14

1039

6

python和c++学习性价比分析
python和c++学习性价比分析

Python易于学习,广泛应用于Web开发、数据科学和人工智能等领域,但性能较低。C语言性能高,适用于对性能要求较高的场景,如游戏开发和系统编程,但学习曲线陡峭,错误处理复杂。想了解更多python的相关内容,可以阅读本专题下面的文章。

2024.03.14

447

5

c语言和c++一样吗
c语言和c++一样吗

c语言和c++是两种不同的编程语言,虽然有相似之处,但存在显著差异。c语言专注于过程式编程和系统级开发,以简洁、高效著称。c++作为c语言的超集,引入了面向对象编程,增强了代码组织和管理能力,但学习曲线也更陡峭。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.03.14

347

5

c语言和c++先学哪个好
c语言和c++先学哪个好

初学者选择学习c语言还是c++语言,需要根据个人学习目标、背景以及编程兴趣和预期应用方向来决定。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.03.14

426

5

c语言和c++的区别和联系
c语言和c++的区别和联系

c语言和c++是计算机科学领域应用广泛的编程语言。虽然它们有着相似的基础,但它们在语言类型、语法功能和内存管理方面存在着显著差异。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.03.14

600

5

c++软件中文更改教程
c++软件中文更改教程

对于 ide,可通过打开设置,找到语言设置,选择中文,并保存更改。对于非 ide 应用程序,可查找设置或选项,选择语言设置,更改为中文,并保存更改。想了解更多c++的相关内容,可以阅读本专题下面的文章。

2024.03.21

1429

9

python和java和c++学习性价比分析
python和java和c++学习性价比分析

Python以其易学性、丰富的库和活跃的社区而著称,适合数据科学、人工智能和Web开发。Java以其跨平台性、企业级应用开发和Android应用开发而闻名。C++以其底层控制能力、高效性能和游戏开发而著称。选择哪种语言取决于个人兴趣、职业方向和特定需求。想了解更多python和java和c++的相关内容,可以阅读本专题下面的文章。

2024.03.22

1237

7

c++和c语言学习顺序推荐
c++和c语言学习顺序推荐

对于初学者,建议先学习C语言,掌握编程基础后再转入C++,便于理解面向对象编程概念。有编程经验者可直接学习C++,快速接触高级编程技术。想了解更多c++和c语言的相关内容,可以阅读本专题下面的文章。

2024.03.25

1325

9

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
GDB Reference Card
GDB Reference Card

共0课时 | 0人学习

《Debugging with GDB》用户手册
《Debugging with GDB》用户手册

共0课时 | 0人学习

Valgrind FAQ
Valgrind FAQ

共0课时 | 0人学习