c++两种方法实现表达式的计算

《c++两种方法实现表达式的计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：网络工程班级：网络1班指导教师：吴亚峰姓名：王嘉宇学号：201214620111目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….01三、源代码………………………………………………………….04四、运行结果……………………………………………………….12五、遇到的问题及解决…………………………………………….13六、心得体会……………………………………………………….14一、设计思想（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一

2、遍扫描中缀表达式，需要一个运算符栈和一个数组。运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。首先将中缀表达式挨个扫描。如果是数字，则直接放在后缀表达式数组中，依次存放。如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，

3、直到遇到左括号为止，此时将左括号从栈顶删除。按此方法，直到后缀表达式转换成功。第二遍扫描后缀表达式，此时需要一个数栈。扫描时如果遇到数字，则直接放到数栈中。如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进行运算符运算。将运算的结果放入栈中。之后接着扫描后缀表达式。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。当栈中只有一个数字时，这个数字就是我们要求的表达式的值。（2）直接计算表达式的值。这种方法需要两个栈，一个运算符栈，一个数栈。只需扫描一遍中缀表达式，边运算

4、边入栈。当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。如果扫描到的是运算符，栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，并从数栈中取出两个数，先取出的放在后面，后取出的放在前面，进行运算符运算，得出结果后，将其放入数栈中。如果栈顶运算符优先级依然高于或等于将要入栈的运算符优先级，仍然进行以上操作，直到栈顶运算符低于将要放入栈中的的运算符的优先级，此时将该运算符入栈。如果扫描到的是左括号，则直接将其入栈。如果扫描到的是右括号，则将栈顶运算符取出，进行以上运算，直到栈顶为左括号，此时将栈顶左括号删除即可，然后

5、将运算结果放入数栈中。当中缀表达式扫描完，并且运算符栈中全部出栈，数栈中只剩一个数字时，即为运算结果。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。二、算法流程图图1是从中缀表达式转为后缀表达式并对后缀表达式进行计算的算法流程图，图中所有图形都是长方形，按箭头顺序依次执行。其中如果箭头向下方向有分叉，则箭头左侧长方形代表“是”，右侧代表“否”。图2是中缀表达式直接计算的算法流程图。按箭头方向执行。图中如果遇到选择类型的语句，则在箭头有分叉的下一行语句中先声明了选项，然后与后面语句逗号隔开。具体流程图如

6、下：14中缀表达式扫描完毕运算符栈中元素全部输出放入后缀表达式数组exp[len]中从后缀表达式中取元素ch=exp[t],t++是否为数存入数栈中从数栈中取出两个数进行运算符运算，得出结果放入数栈输出栈里最终栈顶元素即为所求结束ch是否为（运算符栈为空或者栈运算符优先级低于ch优先级将ch放入运算符栈中将栈顶运算符出栈放入后缀表达式中，直到栈顶元素优先级低于ch优先级，此时将ch入栈将ch入栈将操作符栈中元素取出放入后缀表达式中，直到栈顶元素为（用户输入表达式将表达式赋给str[len]构造运算符栈和数栈扫描中缀表达式ch=str[i],i++ch是否为数将ch直接放入后缀表达式数组中ch

7、是否为+-*/%图1中缀转后缀再计算算法流程图14栈顶元素是否为（是，pop出左括号操作符栈是否为空不是，取出数栈中两个数，计算后存入数栈为空，取出数栈中的数作为返回值不为空，取出数栈中两个数，计算后存入数栈，作为返回值得到存放中缀表达式的数组运算符，与栈顶比较优先级操作符，判断是运算符还是括号数字或小数点，截取子串并将其转换成double型存入数栈中判断字符类型依次取出数组中的每个字符右括号，取出栈顶元素左