一、设计思想
计算算术表达式可以用两种方法实现：
1.中缀转后缀算法
此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算。具体实现方法如下：
（1）中缀转后缀
需要建一个操作符栈op和一个字符数组exp，op栈存放操作符，字符数组用来存放转换以后的后缀表达式。首先，得到用户输入的中缀表达式，将其存入str数组中。
对str数组逐个扫描，如果是数字或小数点，则直接存入exp数组中，当扫描完数值后，在后面加一个#作为分隔符。
如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组，直到遇到左括号，左括号丢掉。然后继续扫描下一个字符，直到遇到str中的结束符号\0，扫描结束。结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空。到此在exp数组最后加结束字符\0。
我们就得到了后缀表达式。
（2）后缀表达式计算
此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。继续扫描，知道扫描结束，此时值栈中的数值就是计算的结果，取出返回计算结果。
2.两个栈实现算法
此算法需要两个栈，一个值栈od，一个操作符栈op。将用户输入的数学表达式存入str数组中，对其数组进行逐个扫描。
当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；
当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。
如果遇到操作符，若op栈为空，直接入栈；若栈不为空，与栈顶元素比较优先等级，若比栈顶操作符优先等级高，直接入op栈，如果低于或等于栈顶优先等级，op栈出栈，再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。继续扫描直到遇到str中的结束字符\0，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈，一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。
二、算法流程图
第一种算法：中缀转后缀算法
其主函数流程图为：
得到用户输入的中
缀表达式
调用calculate 函数计算表达式
返回计算结果
调用trans 函数得到后缀表达
式
图1 主函数算法流程图
中缀转后缀算法流程图如下：
取得字符进行判断
直接放入exp 数组中并在其后加入#分隔
符
与栈顶比较优先等级
如果是操作符
入操作符栈
比栈顶优先级高
出栈存入exp 数组中
不高于栈顶优先级
判断是哪个括号
如果是括号
直接入操作符
栈
如果是左括号
如果是右括号
取出栈顶元素
若栈顶元素不为（
放入exp 数组中
判断是操作符还是括号
如果是操作符或括号
图2 中缀转后缀算法流程图
计算后缀表达式流程图如下：
得到后缀表达式
判断是否为操作符
从值栈取出两个数值，计算结果并存入值栈中
如果为操作符
截取子串并将其转化成double 类型，存入值
栈中
如果是数字或小数点取出最终值栈中的数值，作为返
回值
图3 后缀表达式计算流程图
第二种算法：两个栈算法
其主函数流程图为：
得到用户输入的中
缀表达式
调用calculate 函数计算表达式
返回计算结果
图4 主函数算法流程图
直接计算数学表达式流程图如下：
符号栈是否为空
得到存放中缀表达式的数组str
依次取出数组中的每个字符
判断字符类型
截取子串并将其转化成double 类型，并将其存入值栈中
如果是数字或小数点
如果是操作符或是括号
判断是操作符还是括号
判断是哪个括号
如果是括号
直接入操作符
栈
如果是左括号
取出栈顶元素
如果是右括号栈顶元素是否为（
取出值栈的两个数
值，计算结果后存入值栈中
是
pop 出左括号
不是与栈顶比较优先级
如果是操作符
入操作符栈
取出值栈的两个数值，计算结果后存入值栈中
不高于栈顶优先级取出值栈中的数
值作为返回
取出值栈的两个数值，计算结果后存入值栈中
为空栈非空
图5 直接计算表达式流程图
三、源代码
下面给出的是用中缀转后缀算法实现的程序的源代码：
#include #include #include #include
#define MAXSIZE 100 //定义宏，数组最大长度为100
