怎么做前缀表达式求值的程序和算法？
怎么做前缀表达式求值的程序和算法？
08-09-28 & 发布
什么意思，是不是可以计算诸如(2+3.5)/(23-6+2.44)*9这样的四则运算算式的程序？我用java applet做过一个，如果你要的话可以给加我qq
请登录后再发表评论!合肥学院计算机科学与技术系 课程设计报告学年第二学期 课学学专指业导班教生姓程
数据结构与算法算术表达式求值问题杨松
08计科(2) 王昆仑 张贯虹名 号 级 师课程设计名称2010年6月 题目：（算术表达式求值问题）一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。要求：（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。选作内容：操作数类型扩充到实数。 一、问题分析和任务定义要对一个含有加减乘除四则运算的合法的算术表达式进行求值， ①首先，应了解算术表达式的四则运算的规则： (1)从左向右计算
(2)先乘除，后加减
(3)先括号内，后括号外由此可知，比如算术表达式（7+15）*（23-28/4）的计算顺序，即为
（7+15）*（23-28/4）=22*（23-28/4）=22*（23-7）=22*16=352 ②其次，应明确“算符优先法”的内容：算符优先法就是根据上述四则运算规则确定的优先关系来实现对表达式的编译或解释执行的。一个简单的四则运算表达式由操作数（operand）、运算符（operator）和界限符（delimiter）组成，其中操作数是正整数，运算符只含加、减、乘、除四种，界限符有左右括号和表达式起始、结束符“#”；而且，为了统一算法的描述，将运算符和界限符通称为算符。算符集OP=｛+，-，*，/，（，），#｝。根据上述3条运算规则，在具体的运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系只能是如下3中关系之一：θ1&θ2
θ1的优先级低于θ2
θ1的优先级等于θ2
θ1的优先级高于θ2下表定义了算符之间的这种优先关系。表1 算符之间的优先关系表格说明：1、θ1 、θ2 同“*”、“/”或同为“+”、“-”，则算符θ1的优先级高于θ2 2、θ1为“*”、“/”的优先级高于θ1为“+”、“-” 3、θ1为“+”、“-”、“*”、“/”的优先级高于θ2为“）” 4、θ1为“（”的优先级低于θ2为“+”、“-”、“*”、“/” 5、θ1、θ2同为“（”，θ1的优先级低于θ2；θ1、θ2同为“（”，θ1的优先级高于θ2 6、θ1为“（”且θ2为“）”，或者，θ1、θ2同为“#”，则θ1、θ2的优先级相同7、θ1为“）”、θ2为“（”，或者，θ1为“#”θ2为“）”，或者θ1为“（”θ2为“#”，这3中情况各自之间无优先关系，表示为“ ”，因为表达式中不允许它们相继出现，如果出现，则可以认为出现语法错误。 ③最后，确定算法的基本思想：设置两个工作栈，一个为OPTR栈，存放运算符；另一个为OPND栈，存放操作数或运算结果。则算法的基本思想描述如下：(1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；(2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级后，做如下相应操作：①若栈顶算符θ1的优先级低于刚读入的算符θ2，则将θ2入算符栈OPTR ②若栈顶算符θ1的优先级高于刚读入的算符θ2，则将让θ2出栈；同时，将操作数栈OPND退栈两次，得到两个操作数x、y，对x、y运用θ2进行运算后，再将运算结果如操作数只栈OPND③若栈顶算符算符θ1的优先级等于刚读入的算符θ2，说明左右括号相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符）退栈即可；当算符栈OPTR栈空时，算法结束。二、数据结构的选择和概要设计 数据结构的选择：本程序采用顺序存储结构存储两个栈，即操作数栈（OPND）和算符栈（OPTR）； 概要设计如下： 运算符栈的相关功能函数操作数栈的相关功能函数算术表达式的相关功能函数
主函数表2 运算符栈的功能函数 表3 操作数栈的功能函数表4 算术表达式的相关功能函数 三、详细设计和编码首先本程序定义两个顺序栈：算符栈（OPTR）和操作数栈（OPND）； OPTR栈定义如下： typedef
struct{char
//算符栈的栈底
//算符栈的栈顶
//算符栈的最大长度 }OPTR_STACK; OPND栈定义如下： typedef struct{double
//操作数栈的栈底
//操作数栈的栈顶
//操作数栈的最大长度 }OPND_STACK;然后是算符栈和操作数栈的相关功能函数的详细设计： （1）算符栈的相关功能函数的详细设计如下： 1、int OPTR_InitStack(OPTR_STACK &s)为OPTR栈申请char类型的初始空间STACK_INITSIZE=100个
操作结果：构造一个空栈S，最大长度s.stacksize为100； 2、char OPTR_GetTop(OPTR_STACK &s)初始条件：OPTR栈S已存在且非空（s.top!=s.base）
操作结果：用e= *(s.top-1)返回S的栈顶元素 3、int OPTR_Push(OPTR_STACK &s,char e) 初始条件：OPTR栈S已存在因为考虑到原先申请的空间可能不够，即当OPTR栈的长度已经大于s.stacksize=100，这是需要申请额外的存储空间；每次均用realloc函数申请char类型的额外的STACKINCREMENT=10个存储单元，申请额外空间后的OPTR栈的最大长度s.stacksize增加10；操作结果：插入元素ｅ为新的OPTR栈顶元素，即*s.top++=e； 4、int OPTR_Pop(OPTR_STACK &s,char &e)
初始条件：OPTR栈S已存在且非空；操作结果：OPTR栈顶元素出栈，同时用e保存该栈顶元素，即e=*--s.top；（2）操作数栈的相关功能函数的详细设计如下： 1、int OPND_InitStack(OPND_STACK &s)为OPTR栈申请double类型的初始空间STACK_INITSIZE=100个 操作结果：构造一个空栈S，最大长度s.stacksize为100； 2、double OPND_GetTop(OPND_STACK &s)初始条件：OPND栈S已存在且非空（s.top!=s.base） 操作结果：用e= *(s.top-1)返回S的栈顶元素 3、int OPND_Push(OPND_STACK &s,double e)扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
C++四则运算表达式求值算法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口一个支持函数，浮点数表达式求值算法 - CSDN博客
由于工作原因，需要写一个可以解析字符串表达式的接口，要求支持常用函数，函数多参数，函数嵌套，函数声明如下：
bool eval(const std::string& expr, double *result);
记得大学《数据结构》课程写过表达式求值算法，遂在其上修改。
经典的表达式求值算法基本思想是：先由中缀表达式转换为后缀表达式，然后对后缀表达式求值。但是该算法只支持个位数运算，且不支持对函数的处理，因此这也是本程序需要解决的俩个主要问题。
问题1. 支持浮点运算
这个比较好解决，只需要将原来存放操作数的char型变量改为double类型，存放后缀表达式的字符串改成链表，增加一个read_operand函数，用于从字符串中读取一个double类型的操作数。设计存放后缀表达式的结构体如下：
enum OPTOR_TYPE
OT_OPERATOR, // 操作符
OT_OPERAND,
/* optor类型，用于存放操作符，或操作数 */
struct optor
basic_operator * // 操作符类型，包括 运算符和函数
// 操作数，统一用double表示
OPTOR_TYPE
// 省去其他函数
// 后缀表达式存放在list&optor*&类型的变量里面。
问题2. 支持函数
&针对这个问题，首先想到的是把所有函数替换成函数值，然后对没有函数的表达式求值，这就需要定义两个函数：
double eval_expr(string expr) , // 求包含函数的表达式的值
double eval_func(string expr)，// 求函数的值，函数参数可能是一个包含函数的表达式
然后互相递归调用。由于这种逻辑比较复杂，故弃之不用。
换一种思维方式，前面说的方法是把函数当成操作数，用返回值替换函数，现在把函数当成操作符来处理看会怎样。每个操作符都有一个或多个操作数，函数也是如此，只是操作符和操作数的先后位置不一样，但操作数总是在操作符或函数相邻的左右，由于在中缀表达式转换成后缀表达式的过程中，操作数和操作符是单独处理的（操作数直接取出加到后缀表达式，而操作符需要一些入栈操作），所以操作数在操作符或函数的左还是右就显得不那么重要了。因此要处理函数，只需在中缀转后缀的过程中添加几条规则就可以了：
函数名：直接入栈
& &（ & & ：直接入栈
& & ， & &：操作符出栈，直到遇到（
& & ） & &：操作符出栈，直到遇到（，弹出（，判断栈顶元素是否为函数名，是则出栈。
话不多说，先看一下测试用例：
#include &iostream&
#include &string&
#include &eval.h&
// 测试用例, 用例不是很全，仅作示范
string cases[] = {&sin(3.14/2)+cos(3.14/2)+pow(2,3)+sqrt(3)+lg(100)+ln(7)&, // 测试所有支持的函数
&12.4+2*13-53.345/3+2^3+7%4&,
// 测试基本运算符
&2*sin(3.14/lg(100))+pow(pow(2,1+2),2) + lg(100)&,
// 测试函数嵌套、多参数函数
&2.3+5*4--6&,
// 测试错误表达式
&2+3*sin1(3.14/2)&};
// 测试不支持函数
int main()
int ncase = sizeof(cases)/sizeof(cases[0]);
for(int i = 0; i & ++i)
cout && cases[i] && & = &;
if(eval(cases[i], &result))
cout && result &&
// 输出表达式值
cout && &wrong expression& &&
// 错误的表达式
}以下是程序输出：
用计算器算了以下，值都正确，但有误差，这是浮点计算的特点。
跨平台的源码下载地址（可直接编译成静态库）：/fdxuwei/eval共有 3352 人关注过本帖
标题：谁能做表达式求值啊
求助！！！！！！！！！！！！！！
来　自：南京师范大学
等　级：贵宾
威　望：12
帖　子：4497
专家分：141
我尝试过很多组合结果都是对的...
学习需要安静。。海盗要重新来过。。
等　级：新手上路
帖　子：788
[bo]以下是引用 [un]sunkaidong[/un] 在
19:04 的发言：[/bo]
那个结果问题是我故意的..毕竟我的运算函数只有四个操作符号.....结果有输出啊....没有结果不好判断对错了...哈哈...
兄弟你搞错了，我是帮楼主改的程序，不是你的那个，哈哈。。。你的没问题啦。。
i like linux...
来　自：南京师范大学
等　级：贵宾
威　望：12
帖　子：4497
专家分：141
兄弟,不好意思啊.我还以为你说我呢 哈哈
学习需要安静。。海盗要重新来过。。
等　级：新手上路
帖　子：788
还有楼主说我的不能运行吗？我的是后缀计算表达式哦，你不要输入搞错了。哈哈。。
i like linux...
等　级：新手上路
帖　子：29
ok!!!!!!!!了
谢谢两位啦我已经知道怎么回事了
等　级：贵宾
威　望：59
帖　子：3988
专家分：684
核心就是两个栈
先转换为后缀表达式,然后从中间向外边计算
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
等　级：新手上路
帖　子：29
版主说话总是这么深奥啊 ？？？？？？
等　级：新手上路
上面的两个程序是不是都是不带括号的，要是带括号该怎么写
上面的两个程序是不是都是不带括号的，要是带括号该怎么写
来　自：南京师范大学
等　级：贵宾
威　望：12
帖　子：4497
专家分：141
仔细看...我的是带括号的.....
学习需要安静。。海盗要重新来过。。
等　级：新手上路
帖　子：35
我也写了一个表达式求值的程序，用C写的。有以下功能：&&+ - * 、 （ ）
&&& 1.可以处理负数，若第一个数为负数，则不需要括号；若负数不是第一个数，则需要括号。
&&& 2.可以输入浮点数并计算（double型的）。
&&& 3.可以精确到小数点后6位，若小数点后有多余的零，则输出时，可以屏蔽掉（即不输出0）。
&&& 4.表达式值的范围：-20亿 到 +20亿
&&& 5.除数为0，则输出“除数不能为零”。
&&& 6.若左括号多于或少于右括号，则输出“表达式错误”。
&&& 7.若输入的数据为&&1..2+3&&或&&&1.2.3+4&&,则输出“表达式错误”。
&&& 8.若输入的数据为&&1.+3&&或&&&.3+4&&,则输出“表达式错误”。
&&& 9.可以处理多层括号。
&&& 10.若输入&&& 1+ 01&&，则输出“表达式错误”。
&&& 11.若只输入一个操作数&&或&&多层括号中一个操作数&&，则输出 该操作数。
&&&&&& 若只输入操作数&&或 操作符，则输出 “表达式错误”。
&&&&&& 若输入的操作数&&或 操作符多输了、或少输了， 则输出 “表达式错误”。
&&&&&& 若输入除表达式以外的字符（空格除外），则输出“表达式错误”。
&&& 12.表达式的任何地方都可以输入 空格 。
&&& 13.例：
&&&&&&&&&&&输入&&&&&&&&&&&&&&&&&&&&&&&&输出
&&&&&&&&&&&1/2回车&&&&&&&&&&&&&&&&&&&&& 0.5
&&&&&&&&&&&1/3+2/3回车&&&&&&&&&&&&&&&&&& 1
&&&&&&&&&&&1/3回车&&&&&&&&&&&&&&&&&&&&&0.333333
&&&&&&&&&&&2/3回车&&&&&&&&&&&&&&&&&&&&&0.666667
&&&&&&&&&&&-4.0/2.0回车&&&&&&&&&&&&&&& -2
&&&&&&&&&&&-4.0/(-2.0)/(-1.0)回车&&&&&&-2
&&&你们评评，看还有哪些功能上的漏洞，过几天，我再把代码上传。
版权所有，并保留所有权利。
Powered by , Processed in 0.028730 second(s), 9 queries.
Copyright&, BCCN.NET, All Rights Reserved