下载此文档

逆波兰表达式.ppt


文档分类:经济/贸易/财会 | 页数:约7页 举报非法文档有奖
1/7
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/7 下载此文档
文档列表 文档介绍
【例】逆波兰表达式 rpn (Reverse Polish Notation)
1、问题描述 逆波兰表达式是一种把运算符后置的算术表达式,逆波兰表达式又叫做后缀表达式。 逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算顺序。逆波兰表达式是一种很有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。
例如:正常表达式逆波兰表达式 2+3 2 3 + 2+(3-4) 2 3 4 - + 2+(3-4)*5 2 3 4 – 5 * + 2+5*(3-4) 2 5 3 4 - * +
本题求解逆波兰表达式的值,其中运算符只包括4个,+加、-减、*乘、/除。
2、输入数据 输入为一行,其中运算符和运算数之间都有空格分隔,运算数是1位正整数
3、输出要求 输出为一行,即表达式的值。
4、输入数据样例 2 3 + 8 7 + *
5、输出样例 75
6、解题思路 后缀表达式的求值需要一个堆栈,用此栈来存储后缀表达式中的操作数,计算过程中的中间结果以及最后结果。
基本思路:
扫描后缀算术表达式字符串,每次从字符串中读取一个字符,读到空格不做任何处理,若读到运算符,则表明它的两个操作数已经在栈中,否则读到的字符必为数字,应把它转换为一个正整数存入一个变量中,然后把计算或转换得到的正整数(即该变量的值)压入栈中,依次扫描每个字符并进行上述处理,直到遇到结束符,表明后缀表达式计算完成,最终结果保存在栈中,并且栈中只有这一个值。
function rpn() Begin read(ch) while ( ch <> '\n') do begin case (ch) of case ’+’: r ← pop()+pop() push(r) case ’-’: r ← pop() r ← pop()-r push(r) case ’*’: r ← pop()*pop() push(r) case ’/’: r ← pop() r ← pop()/r push(r) end
if (ch>='0' and ch<='9') then push(ch-’0’) r

逆波兰表达式 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数7
  • 收藏数0 收藏
  • 顶次数0
  • 上传人分享精品
  • 文件大小79 KB
  • 时间2018-04-25