使用栈计算表达式
warning:
这篇文章距离上次修改已过1536天，其中的内容可能已经有所变动。
设计思想
本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、后缀表达式求值。
1. 中缀表达式求值
- 首先定义两个栈，分别用于存取运算符和运算数。
- 然后依次读取表达式的一个字符ch，如果ch是数值，入数值栈
如果ch是运算符，把它与符号栈的栈顶元素的优先级比较：
- 若“<”即优先级低:该运算符进栈，读入下一个字符；
- 若“>”即优先级高，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。
- 若“=”即优先级相等(一般用于“（）”的判定):运算符退栈，消去一个括号读入下一个字符;
- 这时需用到比较运算符优先级的函数：precede(w,ch)
- 重复上述过程，直至整个表达式求值完毕（即符号栈的栈顶元素和当前读入的字符均为”#”），操作数栈的栈顶元素为计算结果。
2. 将中缀表达式转换为后缀表达式
- 从左向右读取表达式，读到运算数把它输出；
读到运算符f，则把符号栈的栈顶元素的算符和f进行优先级比较：
- 若优先级高:该运算符入运算符栈；
- 若优先级相等:从运算符栈退出一个运算符，不输出;
- 若优先级低，从运算符栈退出一个运算符，从运算数栈里输出所有比f优先级高的运算符，直至栈顶算符优先级小于f，f入运算符栈。
- 重复以上流程，一直到最终输出后缀表达式为止。
算法流程图
表达式求值算法流程图.png源代码
#include <stdio.h>
#define StackSize 100
/* 定义字符栈 */
typedef char ElemType;
typedef struct{
ElemType data[StackSize];
int top;
}SqStack;
/* 定义数值栈 */
typedef struct {
double data[StackSize];
int top;
}dstack;
/* 初始化数值栈 */
void DsInit(dstack *s){
s->top = -1;
}
/* 压栈 */
int Dpush(dstack *s, double e){
if (s->top < StackSize - 1){
s->top = s->top + 1;/*若栈不满，则将e进栈*/
s->data[s->top] = e;
return 1;
}else{
return 0;
}
}
/* 出栈 */
double Dpop(dstack *s){
double e;
if (-1 == s->top){
return 1;
}else{
e = s->data[s->top];/*出栈*/
(s->top)--;
return e;
}
}
/* 初始化字符栈 */
void InitStack(SqStack *s){
s->top = -1;
}
/* 压栈 */
int push(SqStack *s, ElemType e){
if (s->top < StackSize - 1){
s->top = s->top + 1;
s->data[s->top] = e;
return 1;
}else{
return 0;
}
}
/* 出栈 */
ElemType pop(SqStack *s){
ElemType e;
if (-1 == s->top){
return 1;
}else{
e = s->data[s->top];
(s->top)--;
return e;
}
}
/* 取栈顶 */
int GetTop(SqStack s, ElemType *e){
if (0 == s.top){
*e = s.data[s.top];
return 0;
}else{
*e = s.data[s.top];
return 1;
}
}
/* 比较优先级 */
int Get_Pri(int mode, char oper){
/* 返回运算符oper代表优先级得整数值，mode为1，表示oper是栈顶运算符，否则是当前运算符 */
int tmp;
switch (oper){
case '#': tmp = 0; break;
case '(': tmp = (mode ? 1 : 6); break;
case '+':
case '-': tmp = (mode ? 3 : 2); break;
case '*':
case '%':
case '/': tmp = (mode ? 5 : 4); break;
case ')': tmp = (mode ? 7 : 1); break;
}
return tmp;
}
char precede(char w, char ch){
/* 判定运算符栈的栈顶运算符w,与当前运算符ch之间的优先关系 */
int grade;
/* 取得栈顶运算符与当前运算符得优先级 */
grade = Get_Pri(1, w) - Get_Pri(0, ch);
if (grade > 0){
return '>';
}else {
if (grade == 0){
return '=';
}else {
return '<';
}
}
}
/* 中缀变后缀的实现函数 */
void change(char E[], char A[]){
SqStack S2;
int i = 0; /*i作为扫描数组E的指针*/
int j = 0; /*j用来指示数组A中待写入字符的位置*/
int k = 0; /*标识上一位是否为'('*/
char ch = E[i]; /*E中第一个字符送给ch*/
char w = '\0'; /*字符串结束字符*/
InitStack(&S2);
push(&S2, '#'); /*栈顶压入'#',以表示空栈*/
while (ch != '#'){ /*判断是否读取到表达式结束标记*/
if (ch >= '0' && ch <= '9' || ch == '.'){ /*数字处理方案*/
k = 0;
while (ch >= '0' && ch <= '9' || ch == '.'){
A[j] = ch;
j++;
i++;
ch = E[i]; /*E中下一个字符送给ch*/
}
A[j] = ' ';
j++; /*给A中的每个操作数后附加一个空格*/
}
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '(' || ch == ')' || ch == '#'){
if (ch == '(') {
k = 1;
}
if (k == 1 && ch == '-') {/*负数处理*/
A[j] = '0';
j++;/*给A中的负数前附加一个0*/
A[j] = ' ';
j++; /*给A中的每个操作数后附加一个空格*/
}
GetTop(S2, &w); /* 字符栈取栈顶 */
while (precede(w, ch) == '>'){/*比较优先级*/
A[j] = w;
j = j + 1;
pop(&S2);/* 字符栈出栈 */
GetTop(S2, &w);
}
if (precede(w, ch) == '<') {
push(&S2, ch); /* 字符栈压栈 */
}else{
if (precede(w, ch) == '='&&w != '#'){
pop(&S2);
GetTop(S2, &w);
}
}
}
if (E[i] != '#') { /*空格处理*/
i++;
}
ch = E[i];
}
while (w != '#'){
A[j] = w;
j++;
pop(&S2);
GetTop(S2, &w);
}
A[j] = '#';/*结束处理*/
A[++j] = '\0';
}
/* 计算后缀表达式的值 */
double comp(char arr[]){
dstack s;
int i = 0;
char ch;
double x = 0, d = 1.0;
DsInit(&s);
ch = arr[i];
while (ch != '#'){
switch (ch){
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
while (ch != ' '){
if ('0' <= ch && ch <= '9'){
while ('0' <= ch && ch <= '9'){
x = x * 10 + (ch - '0');
i = i + 1;
ch = arr[i];
}
}else{
if (ch == '.'){
ch = arr[++i];
while ('0' <= ch && ch <= '9'){
d = d * 10;
x = x + (ch - '0') / d;
ch = arr[++i];
}
}
}
}
break;
case '+':
x = Dpop(&s) + Dpop(&s);
break;
case '-':
x = Dpop(&s);
x = Dpop(&s) - x;
break;
case '*':
x = Dpop(&s)*Dpop(&s);
break;
case '/':
x = Dpop(&s);
x = Dpop(&s) / x;
break;
case '%':
x = Dpop(&s);
x = (double)((int)Dpop(&s) % (int)x);
break;
}
Dpush(&s, x);
x = 0;
i = i + 1;
ch = arr[i];
}
return Dpop(&s);
}
/* 主函数 */
void main(){
char E[100];
char A[100];
printf("请输入表达式并以'#'结束,负数请用'()'标记：");
gets(E);
system("cls");/*清屏*/
change(E, A);
printf("中缀表达式：%s \n", E);
printf("后缀表达式：%s \n", A);
printf("最终结果：%s=%f \n \n", E, comp(A));
system("pause");/*暂停运行,以显示结果*/
system("cls");
main();
}运行结果
表达式求值算法运行结果.png遇到的问题及解决
问题1：忽略了变量的类型，进行了不合法的运算，程序出现异常。
解决方法：严格检查变量类型，养成每次调用变量前先查看变量定义再使用变量的好习惯。
问题2：书写标识符时，忽略了大小写字母的区别，导致程序出现未知错误。
解决方法：后来发现在运行时候左下角会出现“半”，括号是在中文环境下输入的括号，改成英文下的出现正确结果。
问题3：操作数和运算符在一起发生冲突，当混合输入数据和运算符，出现异常，没有结果。
解决方法：使用两个工作栈，一个存储数字，一个存储运算符。
问题4：操作数和运算符在一起发生冲突，当混合输入数据和运算符，出现异常，没有结果。
解决方法：使用两个工作栈，一个存储数字，一个存储运算符。