| 栈的应用之简单表达式求值（C语言附完整代码） | 您所在的位置：网站首页 › 利用栈求表达式的值时怎么求 › 栈的应用之简单表达式求值（C语言附完整代码） |
栈的应用之简单表达式求值（C语言附完整代码）
|
文章目录
前言一、将中缀表达式转化为后缀表达式二、对后缀表达式求值三、完整代码
前言
前面分享了中缀表达式与前，后缀表达式的手算转化方法，今天来分享一下简单表达式的求值，对中缀表达式求值的过程是先将中缀表达式转化为后缀表达式，然后对该后缀表达式进行求值。 步骤： 在将一个中缀表达式转化为后缀表达式时，操作数之间的相对次序是不变的，但运算符的相对次序可能不同，同时可能还要去除括号。因此在转换时需要从左到右扫描算术表达式，将遇到的操作数都直接保存到后缀表达式中，因为需要比较运算符的优先性， 所以将遇到的每一个运算符或者左括号都暂时保存到运算符栈，而且先执行的运算符先出栈。 注意： 1. 在扫描算术表达式时，遇到一个运算符，如果此时栈为空，直接将其进栈，如果栈不为空，则只有该运算符的优先级高于栈顶运算符时才将其进栈，否则依次出栈运算符并存入后缀表达式，直到栈顶运算符的优先级小于该运算符为止，然后再将该运算符进栈。 2. 在扫描算术表达式时，如果遇到 ’ ( ‘,表示一个子表达式的开始，直接将其入栈，如果遇到’ ）‘,表示一个子表达式的结束，需要出栈运算符并存入后缀表达式中，直到栈顶为’ ( '，再将’（ ‘出栈 。 void trans(char *exp,char postexp[]) //将算术表达式exp转换成后缀表达式postexp { char e; SqStack *Optr; //定义运算符栈 InitStack(Optr); //初始化运算符栈 int i=0; //i作为postexp的下标 while (*exp!='\0') //exp表达式未扫描完时循环 { switch(*exp) { case '(': //判定为左括号 Push(Optr,'('); //左括号进栈 exp++; //继续扫描其他字符 break; case ')': //判定为右括号 Pop(Optr,e); //出栈元素e while (e!='(') //不为'('时循环 { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //继续出栈元素e } exp++; //继续扫描其他字符 break; case '+': //判定为加或减号 case '-': while (!StackEmpty(Optr)) //栈不空循环 { GetTop(Optr,e); //取栈顶元素e if (e!='(') //e不是'(' { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e是'(时退出循环 break; } Push(Optr,*exp); //将'+'或'-'进栈 exp++; //继续扫描其他字符 break; case '*': //判定为'*'或'/'号 case '/': while (!StackEmpty(Optr)) //栈不空循环 { GetTop(Optr,e); //取栈顶元素e if (e=='*' || e=='/') //将栈顶'*'或'/'运算符出栈并存放到postexp中 { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e为非'*'或'/'运算符时退出循环 break; } Push(Optr,*exp); //将'*'或'/'进栈 exp++; //继续扫描其他字符 break; default: //处理数字字符 while (*exp>='0' && *exp Pop(Optr,e); //出栈元素e postexp[i++]=e; //将e存放到postexp中 } postexp[i]='\0'; //给postexp表达式添加结束标识 DestroyStack(Optr); //销毁栈 } 二、对后缀表达式求值后缀表达式求值的过程是从左到右扫描后缀表达式postexp，若读取的是一个操作数，将它放入操作数栈，若读取的是一个运算符op，从操作数栈中连续出栈两个操作数，将这两个数进行运算 （假如a第一个出栈，b第二个出栈，计算结果为b op a），将运算结果 （b op a） 放入操作数栈中，当整个后缀表达式扫描完，操作数栈中的栈顶元素就是表达式的计算结果。 double compvalue(char *postexp) //计算后缀表达式的值 { double d,a,b,c,e; SqStack1 *Opnd; //定义操作数栈 InitStack1(Opnd); //初始化操作数栈 while (*postexp!='\0') //postexp字符串未扫描完时循环 { switch (*postexp) { case '+': //判定为'+'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b+a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '-': //判定为'-'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b-a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '*': //判定为'*'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b*a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '/': //判定为'/'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b if (a!=0) { c=b/a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; } else { printf("\n\t除零错误!\n"); exit(0); //异常退出 } break; default: //处理数字字符 d=0; //将连续的数字字符转换成对应的数值存放到d中 while (*postexp>='0' && *postexp char data[MaxSize]; //存放运算符 int top; //栈顶指针 } SqStack; void InitStack(SqStack *&s) //初始化栈 { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } void DestroyStack(SqStack *&s) //销毁栈 { free(s); } bool StackEmpty(SqStack *s) //判断栈是否为空 { return(s->top==-1); } bool Push(SqStack *&s,char e) //进栈元素e { if (s->top==MaxSize-1) return false; s->top++; s->data[s->top]=e; return true; } bool Pop(SqStack *&s,char &e) //出栈元素e { if (s->top==-1) return false; e=s->data[s->top]; s->top--; return true; } bool GetTop(SqStack *s,char &e) //取栈顶元素e { if (s->top==-1) return false; e=s->data[s->top]; return true; } //将算术表达式exp转换成后缀表达式postexp void trans(char *exp,char postexp[]) { char e; SqStack *Optr; //定义运算符栈 InitStack(Optr); //初始化运算符栈 int i=0; //i作为postexp的下标 while (*exp!='\0') //exp表达式未扫描完时循环 { switch(*exp) { case '(': //判定为左括号 Push(Optr,'('); //左括号进栈 exp++; //继续扫描其他字符 break; case ')': //判定为右括号 Pop(Optr,e); //出栈元素e while (e!='(') //不为'('时循环 { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //继续出栈元素e } exp++; //继续扫描其他字符 break; case '+': //判定为加或减号 case '-': while (!StackEmpty(Optr)) //栈不空循环 { GetTop(Optr,e); //取栈顶元素e if (e!='(') //e不是'(' { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e是'(时退出循环 break; } Push(Optr,*exp); //将'+'或'-'进栈 exp++; //继续扫描其他字符 break; case '*': //判定为'*'或'/'号 case '/': while (!StackEmpty(Optr)) //栈不空循环 { GetTop(Optr,e); //取栈顶元素e if (e=='*' || e=='/') //将栈顶'*'或'/'运算符出栈并存放到postexp中 { postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e为非'*'或'/'运算符时退出循环 break; } Push(Optr,*exp); //将'*'或'/'进栈 exp++; //继续扫描其他字符 break; default: //处理数字字符 while (*exp>='0' && *exp Pop(Optr,e); //出栈元素e postexp[i++]=e; //将e存放到postexp中 } postexp[i]='\0'; //给postexp表达式添加结束标识 DestroyStack(Optr); //销毁栈 } //操作数栈基本运算 typedef struct { double data[MaxSize]; //存放数值 int top; //栈顶指针 } SqStack1; void InitStack1(SqStack1 *&s) //初始化栈 { s=(SqStack1 *)malloc(sizeof(SqStack1)); s->top=-1; } void DestroyStack1(SqStack1 *&s) //销毁栈 { free(s); } bool StackEmpty1(SqStack1 *s) //判断栈是否为空 { return(s->top==-1); } bool Push1(SqStack1 *&s,double e) //进栈元素e { if (s->top==MaxSize-1) return false; s->top++; s->data[s->top]=e; return true; } bool Pop1(SqStack1 *&s,double &e) //出栈元素e { if (s->top==-1) return false; e=s->data[s->top]; s->top--; return true; } bool GetTop1(SqStack1 *s,double &e) //取栈顶元素e { if (s->top==-1) return false; e=s->data[s->top]; return true; } //计算后缀表达式的值 double compvalue(char *postexp) { double d,a,b,c,e; SqStack1 *Opnd; //定义操作数栈 InitStack1(Opnd); //初始化操作数栈 while (*postexp!='\0') //postexp字符串未扫描完时循环 { switch (*postexp) { case '+': //判定为'+'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b+a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '-': //判定为'-'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b-a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '*': //判定为'*'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b*a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '/': //判定为'/'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b if (a!=0) { c=b/a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; } else { printf("\n\t除零错误!\n"); exit(0); //异常退出 } break; default: //处理数字字符 d=0; //将连续的数字字符转换成对应的数值存放到d中 while (*postexp>='0' && *postexp char exp[]="(50-20)/(8+2)"; char postexp[MaxSize]; trans(exp,postexp); printf("中缀表达式:%s\n",exp); printf("后缀表达式:%s\n",postexp); printf("表达式的值:%g\n",compvalue(postexp)); return 0; }参考资料：李春葆《数据结构教程》（第五版） |
【本文地址】
公司简介
联系我们