用栈实现表达式计算.doc

《用栈实现表达式计算.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用两种方式实现表达式自动计算一、设计思想算法一：利用栈将中缀表达式转化成后缀表达式再进行计算。（1）构造char类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Min_Back()）。（3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表达式转换成后缀表达式的函数。函数

2、中利用构建的栈以及栈的相关函数对运算符进行操作：先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘—’并且现有运算符为‘*’、‘/’或‘%’又或是现有运算符为‘（’，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。循环结束后，将栈中的运算符全部依次输出，最后将后缀表达式传递给求值函数（countfor()），再销毁栈。（4）求值函数中首先是利用strtod()函数将数字字符串转换成double类型的数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当

3、遇到运算符时，就从数字栈中“扔出”两个数字进行相应的运算，循环结束后，将数字栈中的数字“扔出”，并输出成为表达式最终的结果。算法二：利用创建的两个栈直接对表达式进行计算。（1）分别构建一个char类型和一个double类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Countfor()

4、）。（3）在Countfor()函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为’’。在循环中如果元素为数字、点或者#，将元素赋给新的数组Consist[]，再判断下一个元素是否为#，若是则利用strtod()函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组Consist[]；否则，继续判断。若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘—’并且现有元素为‘*’、‘/’或‘%’又或是现有元素为‘（’，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运算符出栈直到‘（’-23-用两种

5、方式实现表达式自动计算出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。（4）Judge()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。二、算法流程图算法一：利用栈将中缀表达式转化成后缀表达式再进行

6、计算。图1为算法一中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。是否是将一个#号传给数组str_pass[]元素不是数字或’.’传给数组str_pass[]，原数组下脚标+1否传给数组str_pass[]将新的表达式传递给Countfor()函数是对表达式进行循环开始用户输入表达式元素为’’元素为数字或’.’否结束图1中缀转后缀表达式算法main()函数流程图图2为算法一中Mid_Back()函数的算法流程图，主要功能为：将中缀表达式转换成后缀表达式。-23-用两种方式实现表达式自动计算将栈进行循环栈不为空否是输出后缀表达式结束将表达式传给求值函

7、数countfor()运算符出栈否声明并创建一个栈开始对表达式进行循环将元素传给数组Ba_str[]是是现有元素不为’=’元素为数字、点或者’#’看栈顶是元素进栈否栈为空或栈顶为’(’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’(’元素为’)’出栈直到’(’出栈是否出栈并赋给Ba_str[]看栈顶是元素进栈否出栈，将现有元素进栈否栈为空或栈顶为’(’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’(’图2中缀转后缀表达式