0

0

C++如何实现中缀表达式求值_C++利用栈结构解析数学算式【数据结构】

尼克

尼克

发布时间:2026-02-05 15:48:44

|

203人浏览过

|

来源于php中文网

原创

不能直接用std::stack逐字符扫描,因需处理运算符优先级、括号嵌套、负号歧义、多位整数等;必须用双栈+优先级规则(如getPrecedence)、上下文识别负号、空格跳过及栈空/除零检查。

c++如何实现中缀表达式求值_c++利用栈结构解析数学算式【数据结构】

为什么不能直接用 std::stack 逐字符扫描就完事?

中缀表达式求值看似只是“遇到数字压、遇到运算符弹栈计算”,但实际要处理:运算符优先级(+* 不同)、括号嵌套、负号与减号歧义(如 -53-5)、多位整数(123 不是三个字符)。如果只用一个 std::stack 存操作数,另一个 std::stack 存运算符,不加规则控制弹栈时机,结果大概率错在 2+3*4 算成 20 而不是 14

关键判断依据是:当前运算符和栈顶运算符的优先级关系。必须定义明确的比较逻辑,比如用函数 getPrecedence(char op) 返回数值(( 设为 0,+/- 为 1,*// 为 2),再决定是压栈还是先弹出高优先级运算符计算。

如何安全处理左括号、右括号和负号?

括号不是运算符,而是作用域标记;负号不是二元运算符,是单目前缀。硬把它们塞进同一套优先级规则会出问题。

  • ( 压入运算符栈时,不触发任何计算 —— 它只是“记个位置”
  • 遇到 ) 时,持续弹出并计算,直到弹出第一个 ((不参与计算,仅丢弃)
  • 负号识别需结合上下文:开头、左括号后、或上一个字符是运算符(如 +, -, *, /),此时下一个数字应取负 —— 建议在词法解析阶段就合并处理,比如把 "-5" 直接转成整数 -5,而不是压入 '-' 再试图“特殊匹配”

示例片段:

if (ch == '-' && (i == 0 || isOperator(expr[i-1]) || expr[i-1] == '(')) { /* 解析负数 */ }

立即学习C++免费学习笔记(深入)”;

Face++旷视
Face++旷视

Face⁺⁺ AI开放平台

下载

std::stack 实现时,哪些细节容易崩?

崩点往往不在算法逻辑,而在边界和类型转换:

  • 数字解析:循环读取连续数字字符后,别忘了用 std::stoi() 或手动累加,且注意溢出(题目若无说明可暂不处理,但心里要有数)
  • 除零检查:在执行 / 前必须判断第二个操作数是否为 0,否则运行时崩溃或未定义行为
  • 栈空检查:每次 pop() 前务必 if (!stack.empty()),尤其处理右括号或结尾时,非法表达式(如 "2+)")会导致栈空异常
  • 最后清空:表达式扫完后,运算符栈可能还有残留(如 "1+2+3"),必须全部弹出计算,不能只依赖循环结束

要不要手写栈?std::stack 够用吗?

够用,而且更安全。除非题目强制要求“不使用 STL”,否则没必要重造轮子。但要注意:std::stack 默认基于 std::deque,你无法直接遍历或查看栈底;如果调试时想打印中间状态,得额外用 vector 模拟,或者临时把元素倒腾出来 —— 这属于调试技巧,不影响核心逻辑。

真正影响可维护性的,是把“运算符优先级判断”、“括号状态机”、“数字提取”这些职责混在一个 while 循环里。建议拆成小函数:parseNumber()precedenceCompare()doOperation()。哪怕只有几行,也能让主循环清晰到一眼看出控制流。

最常被忽略的一点:输入字符串带空格。别假设输入干净,isspace() 判断跳过才是常态。

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

1507

2023.10.24

Go语言中的运算符有哪些
Go语言中的运算符有哪些

Go语言中的运算符有:1、加法运算符;2、减法运算符;3、乘法运算符;4、除法运算符;5、取余运算符;6、比较运算符;7、位运算符;8、按位与运算符;9、按位或运算符;10、按位异或运算符等等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

233

2024.02.23

php三元运算符用法
php三元运算符用法

本专题整合了php三元运算符相关教程,阅读专题下面的文章了解更多详细内容。

127

2025.10.17

if什么意思
if什么意思

if的意思是“如果”的条件。它是一个用于引导条件语句的关键词,用于根据特定条件的真假情况来执行不同的代码块。本专题提供if什么意思的相关文章,供大家免费阅读。

794

2023.08.22

while的用法
while的用法

while的用法是“while 条件: 代码块”,条件是一个表达式,当条件为真时,执行代码块,然后再次判断条件是否为真,如果为真则继续执行代码块,直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容,供大家免费下载体验。

98

2023.09.25

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

381

2023.08.03

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

213

2023.09.04

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

1507

2023.10.24

java连接字符串方法汇总
java连接字符串方法汇总

本专题整合了java连接字符串教程合集,阅读专题下面的文章了解更多详细操作。

2

2026.02.05

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
国外Web开发全栈课程全集
国外Web开发全栈课程全集

共12课时 | 1.0万人学习

进程与SOCKET
进程与SOCKET

共6课时 | 0.4万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号