用两种方式实现表达式自动计算
一、设计思想
计算表达式有两种方式，第一种是先算后缀表达式，再计算结果，第二种是直接计算中缀表达式求值，下面介绍两种方式的设计思想。
（1）先算后缀表达式，再计算结果。程序先定义了两个栈odlist和oplist，分别用作数字栈和运算符栈，并用指针*od和*op访问这两个栈，同时定义两个栈的入栈、出栈和看栈顶的函数，再定义一个判断是否是操作符的函数int is_op()、一个比较运算符优先级的函数int level()和计算两个数字运算结果的函数double re()。
主函数中定义字符型的数组inorder[100]和postorder[100]分别用于存放中缀表达式和转换后的后缀表达式，整型的inpos和postpos分别表示中缀表达式的扫描索引和后缀表达式的扫描索引。
然后进行中缀表达式转换为后缀表达式。用while循环扫描inorder[100]数组，如果是数字字符，直接将其逐个复制给postorder[postorder++]，并在最后加一个空格用于和下一个数字区分；如果是运算符，此运算符优先级比op栈栈顶优先级大时直接入栈，否则将op栈栈顶取出放入postorder[postorder++]中，直到此运算符比栈顶优先级高，然后将次运算符入栈；如果是左括号，无条件入栈；如果是右括号，将op栈的栈顶元素出栈并放入postorder[100]中，循环执行上面的操作，直到栈顶为右括号，然后将左括号出栈。当while循环结束后，如果op栈不为空时，将op栈中的运算符逐个出栈并放入postorder[postorder++]中。此时字符数组postorder[100]中存放的就是已经转换为后缀表示的表达式，每一串数字字符结束后，都在后面用空格分割开来，防止和下一个数字叠加。
再下来进行进行后缀表达式的计算。用while循环扫描字符数组postorder[100]，只要不遇到’\\0’，就一直从0往后扫描。如果遇到数字，就用atof()函数将数字字符转换为double类型，并将此数字压入od栈中；如果遇到运算符，就从od栈中先后取出两个数字，先取出的在后面，后取出的在前面，用函数double re()计算两个数的运算结果，将结果重新压入od栈中。当这个while循环结束后，od栈栈顶存放的就是后缀表达式的计算结果。
最后将存放在od栈栈顶的结果赋值给double类型的result，并在屏幕上输出。 （2）直接计算结果。程序先定义了两个栈odlist和oplist，分别用作数字栈和运算符栈，并用指针*od和*op访问这两个栈，同时定义两个栈的入栈、出栈和看栈顶的函数，再定义一个判断是否是操作符的函数int is_op()、一个比较运算符优先级的函数int level()和计算两个数字运算结果的函数double re()。
主函数中定义字符类型的数组inorder[100]，用来表示中缀表达式，整型的inpos用来表示数组inorder[100]的扫描索引。
然后开始扫描中缀表达式。从0开始扫描中缀表达式所在的数组inorder[100],直到遇到’\\0’结束。在扫描过程中，如果遇到数字字符，用函数atof()将这一串数字字符转换为double类型的数字，并压入od栈中；如果遇到运算符，先判断此运算符是否可以入栈，如果不可以，将栈顶出栈，同时从od栈总取出两个数字，先取出的放在出栈的运算符符号后面，后取出的放在出栈的运算符前面，计算两个数字的运算结果，并将计算结果重新压入od栈中，重复执行上面的操作，直到此操作符可以入栈，然后将这个操作符压入op栈中。此while循环结束后，中缀表达式已经扫描完毕，数字和运算符存储在栈中。
接下来进行清空op栈的操作。如果op栈不为空，则将op栈栈顶出栈，同时从od栈中取出两个数字，先取出的放在出栈的运算符符号后面，后取出的放在出栈的运算符前面，计算两个数字的运算结果，并将计算结果重新压入od栈中，重复执行上面的操作，直到op栈为空。此while循环结束后，od栈栈顶中存放的就是中缀表达式的运算结果。
最后将od栈栈顶元素的值赋值个double类型的result，并在屏幕上输出。
- 1 -
用两种方式实现表达式自动计算
二、算法流程图
下面分别是两种算法的详细流程图：
（1）先算后缀表达式，再算结果的算法流程图。 开始 接收表达式 扫描索引加1 否 继续扫描表达式扫描 字符不等于‘\\0’ 表达式 完成 op栈不是空 是左括号 否 是 入op栈 判断运算符 扫描op栈出栈，与od 后缀表达式转换索栈两数计算，结 完成，进行计算 字符逐个复制是数字字符 引果压入od栈 加 给postorder， 最后加空格 出栈计算，是右括号 是’\\0’ 直到栈顶是 判断运算符 左括号出栈 扫左括号 描索 运算结束，引是数字字符 是 是运算符 加输出栈顶结能入op栈 入op栈 转为数字压入od栈 果 否 是运算符 是 op栈顶出栈，复入栈 能入op栈 制到postorder 否 op栈出栈，与od 栈两数计算，结果 压入od栈 结束 1 1 图1 先算后缀，再算结果的算法流程图
- 2 -
用两种方式实现表达式自动计算
（2）直接计算的算法流程图。
开始 接收表达式 扫描索引加1 是 继续扫描字符不等于’\\0’ 表达式 是左括号 判断运算符 入op栈 是 是数字字符 字符转换为数 字，压入od栈 op栈出栈，直是右括号 计算表达式 左括号出栈 到栈顶为左完成，od栈 括号 顶出栈，并 在屏幕上输是运算符 是 出 运算符入 能入op栈 op栈 否 op栈顶出栈，od栈 依次出两数，计算 结果压入od栈中 图2 直接计算的算法流程图
否 表达式扫描完成 否 op栈是空 op栈顶出栈，od栈依次出两数，计算结果压入od栈中 结束 三、源代码
下面给出的是先算后缀表达式，再计算结果的程序的源代码：
/****************************************/ /* 程序名称：stack_1.c */ /* 计算多项式，先求后缀表达式，再求结果*/ /***************************************/ #include \#include \#include \
- 3 -
用两种方式实现表达式自动计算
#define MAX 100
struct opnode { };
struct odnode
/*声明od栈*/
char str[100]; int top_op;
/*声明op栈*/
/*定义栈的最大长度*/
{ double num[100]; int top_od;
};
void push_op(struct opnode *op,char c) { if(op->top_op>=MAX-1)
{ } else
{ op->top_op++; op->str[op->top_op]=c; }
}
void pop_op(struct opnode *op)
{ if(op->top_op<=-1)
{ }
else
{ op->top_op--;
}
}
char top_op(struct opnode *op)
{ return(op->str[op->top_op]);
}
/***************/
void push_od(struct odnode *od,double d) {
if(od->top_od>=MAX-1)
/*op栈的进栈函数*/
/*如果栈为满，不进行操作*/ /*如果栈不满，进行压栈操作*/
/*op栈的出栈函数*/
/*如果栈为空，不进行操作*/ /*如果栈不为空，进行出栈操作*/
/*op栈的看栈顶函数*/
/*od栈的进栈操作*/
/*如果栈为满，不进行操作*/ - 4 -
用两种方式实现表达式自动计算
{ } else { od->top_od++;
od->num[od->top_od]=d;
/*如果栈不为满，进行进栈操作*/
}
}
void pop_od(struct odnode *od) { if(od->top_od<=-1)
{ }
else
{ od->top_od--;
}
}
double top_od(struct odnode *od) { return(od->num[od->top_od]);
}
/*判断是否为运算符*/ int is_op(char op)
{ switch(op)
{ case '(':return 1;break; case ')':return 1;break; case '+':return 1;break; case '-':return 1;break; case '*':return 1;break; case '/':return 1;break; case '%':return 1;break; default:return 0;break; }
}
/*判断运算符优先级*/ int level(char op)
{
/*od栈的出栈函数*/
/*如果栈为空，不进行操作*/ /*如果栈不为空，进行出栈操作*/
/*使od栈的top_od-1*/
/*od栈的看栈顶的函数*/
/*定义函数判断是否是运算符，返回整型*/
/*用switch函数选择，op为运算符*/
/*如果是操作符，返回1*/ /*如果不是操作符，返回0*/
/*定义函数判断运算符的栈内优先级，返回整型*/
- 5 -