1. IT分享知识网首页
  2. 未分类

栈的应用-表达式求值

老牧童 • • 未分类 • 阅读 9

栈的应用-表达式求值表达式求值

大家好，欢迎来到IT知识分享网。

1、中缀表达式转前缀表达式（手算）

在这里插入图片描述
注：在中缀表达式转前缀表达式的过程中，从右向左扫描表达式，只要右边的运算符能先计算，就优先计算右边的。这样能保证得到的后缀表达式是唯一的，并且是从右向左依次生效的！

2、前缀表达式的计算（机算）

使用栈实现前缀表达式的计算（先出栈的是左操作数） （1）、从右往左扫描下一个元素，直到处理完所有的元素 （2）、若扫描到操作数压入栈，并回到（1）；否则（3） （3）、若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，将结果压回栈顶，并回到（1） （4）、往复循环上述步骤，直到处理完所有的元素的，栈中必将只有一个元素，否则前缀表达式有误，是不合法的

注意，由于是从右向左扫描下一个元素执行操作，所以先进栈的是右操作数，后进的是左操作数，但是由于栈先进后出的特性，所以遇到运算符先出栈的是左操作数！
在这里插入图片描述

3、中缀表达式转后缀表达式（手算）

在这里插入图片描述
在中缀表达式转后缀表达式的过程中，从左向右扫描扫描表达式，只要左边的运算符能先计算，就优先计算左边的。这样能保证得到的后缀表达式是唯一的，并且是从左向右依次生效的！

4、后缀表达式的计算（手算）

在这里插入图片描述

5、后缀表达式计算（机算）

在这里插入图片描述

（4）、往复循环上述步骤，直到处理完所有的元素的，栈中必将只有一个元素，否则后缀表达式有误，是不合法的

6、中缀表达式转后缀表达式（机算）

初始化一个栈，用来保存暂时还不能确定运算顺序的运算符 从左到右扫描处理各个元素，直到末尾，可能会遇到的三种情况： （1）、遇到操作数。直接加入到后缀表达式 （2）、遇到界限符 遇到“（”直接加入栈 遇到“）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止（注意：“（”是不加入后缀表达式中的），因为当前的界限符“）”肯定比栈顶运算符+、-、*、）的优先级低，所以直接依次弹出栈中优先级高于“）”的所有运算符，直到弹出优先级相同的栈顶元素“（” （3）、遇到运算符（查看运算符栈） 若当前运算符比栈顶运算符优先级低，依次弹出栈中优先级高于或者等于当前运算符的所有运算符，并加入到后缀表达式中，之后再将当前运算符压入栈 若当前运算符比栈顶运算符优先级高，则直接将当前运算符入栈 若栈顶元素为“（”，则直接将当前元算符压入栈中（因为当前的运算符+、-、*、/、（的优先级肯定比栈顶元素“）的优先级高”） 若 栈中为空，则直接将当前运算符压入栈中 （4）、按照上面的的方法处理完所有的字符之后，将栈中剩余的运算符依次弹出栈，并加入后缀表达式！

7、中缀表达式的计算

一边生成后缀表达式，同时使用后缀表达式的机算方法来计算后缀表达式

首先需要初始化两个栈，一个是操作数栈，一个是运算符栈 从左往右依次扫描算式表达式中的每一个字符 若是扫描到操作数，直接压入操作数栈 若是扫描到运算符或者界限符，按照“中缀表达式转后缀表达式”相同的逻辑压入运算符栈（但是期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再次压回操作数栈） 从左往右扫描完之后，若是运算符栈为空且操作数栈栈底只有一个元素，那么该中缀表达式合法，否则该中缀表达式是不合法的！

严蔚敏版中缀表达式算法步骤

在这里插入图片描述

8、中缀表达式的算法实现（c版本）

自定义链栈的头文件operator.h，用于实现栈的各种操作

#ifndef SQLIST_H #define SQLIST_H #include<stdio.h> #include<stdlib.h> //malloc函数的头文件  //链栈的存储结构 typedef struct StackNode{ 
    char data; struct StackNode*next; }StackNode,*LinkStack; //初始化链栈  void InitStack(LinkStack &S){ 
    //构造一个不带头结点的空栈，使栈顶指针置空  S = NULL; } //入栈操作 void Push(LinkStack &S,char e){ 
    //在栈顶插入元素e StackNode *p; //p = (StackNode*) malloc(sizeof(StackNode)); //生成新节点  p = new StackNode; p->data = e; //将新节点数据域置为e  p->next = S; //将新节点插入栈顶 S = p; //修改栈顶指针 } //出栈操作 void Pop(LinkStack &S,char &e){ 
    StackNode *p; if (S == NULL) printf("\n栈空，出栈操作失败！\n"); e = S->data; //将栈顶元素赋值给e，用于返回元素 p = S; //用p临时保存栈顶元素空间，以备释放  S = S->next; //修改栈顶指针 //free(p);  delete p; //释放原栈顶元素的空间  } //取栈顶元素 char GetTop(LinkStack S){ 
    if (S != NULL) return S->data; } #endif

主程序中使用#include “operator.h” 引入自定义栈

In函数实现

//判断读入的字符ch是否为运算符 int In(char ch){ 
    switch(ch){ 
    case '+': case '-': case '*': case '/': case '(': case ')': case '[': case ']': case '#': return TRUE; break; default : return FALSE; } }

Operate函数实现

//运算函数 char Operate(char operand1,char theta,char operand2){ 
    //0 48 //1 49 //2 50  //3 51  //4 52 //5 53 //6 54 //7 55 //8 56 //9 57 char result; int a=operand1-'0',b=operand2-'0'; //将char类型转换为int类型  switch(theta){ 
    case '+': result = a+b+'0'; //将int类型转换为char类型  break; case '-': result = a-b+'0'; break; case '*': result = a*b+'0'; break; case '/': result = a/b+'0'; break; case '%': result = a%b+'0'; break; } return result; }

Precede函数实现

//判断运算符栈的栈顶元素与读入的运算符之间的优先关系 char Precede(char OperatorStackTopElme,char CurrentChar){ 
    char result; switch(CurrentChar) { 
    case '+': case '-': if(OperatorStackTopElme=='('||OperatorStackTopElme=='#') result='<'; else result='>'; break; case '*': case '/': if(OperatorStackTopElme=='*'||OperatorStackTopElme=='/'||OperatorStackTopElme==')') result='>'; else result='<'; break; case '(': if(OperatorStackTopElme==')'){ 
    printf("ERROR\n"); exit(ERROR); } else result='<'; break; case ')': switch(OperatorStackTopElme){ 
    case '(': result='='; break; case '#': printf("ERROR\n"); exit(ERROR); default: result='>'; } break; case '#': switch(OperatorStackTopElme){ 
    case '#': result='='; break; case '(': printf("ERROR\n"); exit(ERROR); default: result='>'; } } return result; }

注意Precede函数实现要借助算符优先表

下列表格中行符号是运算符栈的栈顶元素OperatorStackTopElme，列符号是当前被扫描运算符号CurrentChar

在这里插入图片描述

核心算法实现

//求值函数 char EvaluateExpression(){ 
    //算数表达式求值的算符优先算法，设OPTR和OPAD分别为运算符栈和操作数栈 LinkStack OPTR; InitStack(OPTR); //初始化运算符栈 LinkStack OPAD; InitStack(OPAD); //初始化操作数栈  Push(OPTR,'#'); //将表达式起始符压入栈中 cout<<"\n栈底元素："<<GetTop(OPTR)<<endl; cout<<"\n输入表达式，表达式以#结尾："; char ch; cin>>ch; while(ch!='#' || GetTop(OPTR)!='#'){ 
    //表达式没有扫描完毕或者OPTR的栈顶元素不为# if(!In(ch)) { 
    //当前读入的不是运算符即为操作数，进操作数栈  cout<<"\n当前入栈元素："<<ch<<endl; Push(OPAD,ch); cin>>ch; } else{ 
    switch(Precede(GetTop(OPTR),ch)){ 
    //比较当前读到的运算符与运算符栈栈顶元素的优先级关系 case '<': //当前的运算符ch比运算符栈的栈顶元素的优先级高 cout<<"\n当前入栈元素："<<ch<<endl; Push(OPTR,ch); //直接将当前运算符入栈 cin>>ch; //继续扫描下一位 break; case '>': //当前的运算符ch比运算符栈的栈顶元素的优先级低 char theta; char FirstOperand,SecondOperand; Pop(OPTR,theta); //弹出OPTR栈顶的运算符 cout<<"\n当前出栈运算符："<<theta<<endl; Pop(OPAD,SecondOperand); //弹出OPAD栈顶的第一个元素  cout<<"\n当前出栈的第二个操作数："<<SecondOperand<<endl; Pop(OPAD,FirstOperand); //弹出OPAD栈顶的第二个元素  cout<<"\n当前出栈的第一个操作数："<<FirstOperand<<endl; Push(OPAD,Operate(FirstOperand,theta,SecondOperand)); //将运算结果压入OPAD栈  cout<<"\n计算结果："<<FirstOperand<<" "<<theta<<" "<<SecondOperand<<" = "<<Operate(FirstOperand,theta,SecondOperand)<<endl; cout<<"\n计算结果栈顶元素："<<GetTop(OPAD)<<endl; break; case '=': //OPTR的栈顶元素是“（”且ch是“）” char x; Pop(OPTR,x); //弹出OPTR栈顶的“（”，读入下一个字符  cout<<"\n左括号遇见右括号，去掉括号："<<x<<"--------"<<ch<<endl; cin>>ch; cout<<"\n去掉括号之后读入的元素为："<<ch<<endl; break; } } } return GetTop(OPAD); }

主程序代码实现

#include<stdio.h> #include<stdlib.h> //malloc函数的头文件 #include<iostream>  using namespace std; #define TRUE 1; #define FALSE 0 #define ERROR 0 #include "operator.h" //自定义栈  //判断读入的字符ch是否为运算符 int In(char ch){ 
    switch(ch){ 
    case '+': case '-': case '*': case '/': case '(': case ')': case '[': case ']': case '#': return TRUE; break; default : return FALSE; } } //判断运算符栈的栈顶元素与读入的运算符之间的优先关系 char Precede(char OperatorStackTopElme,char CurrentChar){ 
    char result; switch(CurrentChar) { 
    case '+': case '-': if(OperatorStackTopElme=='('||OperatorStackTopElme=='#') result='<'; else result='>'; break; case '*': case '/': if(OperatorStackTopElme=='*'||OperatorStackTopElme=='/'||OperatorStackTopElme==')') result='>'; else result='<'; break; case '(': if(OperatorStackTopElme==')'){ 
    printf("ERROR\n"); exit(ERROR); } else result='<'; break; case ')': switch(OperatorStackTopElme){ 
    case '(': result='='; break; case '#': printf("ERROR\n"); exit(ERROR); default: result='>'; } break; case '#': switch(OperatorStackTopElme){ 
    case '#': result='='; break; case '(': printf("ERROR\n"); exit(ERROR); default: result='>'; } } return result; } //运算函数 char Operate(char operand1,char theta,char operand2){ 
    //0 48 //1 49 //2 50  //3 51  //4 52 //5 53 //6 54 //7 55 //8 56 //9 57 char result; int a=operand1-'0',b=operand2-'0'; //将char类型转换为int类型  switch(theta){ 
    case '+': result = a+b+'0'; //将int类型转换为char类型  break; case '-': result = a-b+'0'; break; case '*': result = a*b+'0'; break; case '/': result = a/b+'0'; break; case '%': result = a%b+'0'; break; } return result; } //求值函数 char EvaluateExpression(){ 
    //算数表达式求值的算符优先算法，设OPTR和OPAD分别为运算符栈和操作数栈 LinkStack OPTR; InitStack(OPTR); //初始化运算符栈 LinkStack OPAD; InitStack(OPAD); //初始化操作数栈  Push(OPTR,'#'); //将表达式起始符压入栈中 cout<<"\n栈底元素："<<GetTop(OPTR)<<endl; cout<<"\n输入表达式，表达式以#结尾："; char ch; cin>>ch; while(ch!='#' || GetTop(OPTR)!='#'){ 
    //表达式没有扫描完毕或者OPTR的栈顶元素不为# if(!In(ch)) { 
    //当前读入的不是运算符即为操作数，进操作数栈  cout<<"\n当前入栈元素："<<ch<<endl; Push(OPAD,ch); cin>>ch; } else{ 
    switch(Precede(GetTop(OPTR),ch)){ 
    //比较当前读到的运算符与运算符栈栈顶元素的优先级关系 case '<': //当前的运算符ch比运算符栈的栈顶元素的优先级高 cout<<"\n当前入栈元素："<<ch<<endl; Push(OPTR,ch); //直接将当前运算符入栈 cin>>ch; //继续扫描下一位 break; case '>': //当前的运算符ch比运算符栈的栈顶元素的优先级低 char theta; char FirstOperand,SecondOperand; Pop(OPTR,theta); //弹出OPTR栈顶的运算符 cout<<"\n当前出栈运算符："<<theta<<endl; Pop(OPAD,SecondOperand); //弹出OPAD栈顶的第一个元素  cout<<"\n当前出栈的第二个操作数："<<SecondOperand<<endl; Pop(OPAD,FirstOperand); //弹出OPAD栈顶的第二个元素  cout<<"\n当前出栈的第一个操作数："<<FirstOperand<<endl; Push(OPAD,Operate(FirstOperand,theta,SecondOperand)); //将运算结果压入OPAD栈  cout<<"\n计算结果："<<FirstOperand<<" "<<theta<<" "<<SecondOperand<<" = "<<Operate(FirstOperand,theta,SecondOperand)<<endl; cout<<"\n计算结果栈顶元素："<<GetTop(OPAD)<<endl; break; case '=': //OPTR的栈顶元素是“（”且ch是“）” char x; Pop(OPTR,x); //弹出OPTR栈顶的“（”，读入下一个字符  cout<<"\n左括号遇见右括号，去掉括号："<<x<<"--------"<<ch<<endl; cin>>ch; cout<<"\n去掉括号之后读入的元素为："<<ch<<endl; break; } } } return GetTop(OPAD); } //主函数入口  main(){ 
    cout<<"\n运算结果如下："<<EvaluateExpression()<<endl; }

结果演示

在这里插入图片描述

算法分析

此算法从头到尾扫描整个算式表达式中的每一个字符，若算式表达式的字符串长度是n，该算法的时间复杂度为O（n）。算法在运行时所占用的辅助空间主要取决于OPTR栈和OPAD栈的大小，显然他们的空间大小之和不会超过n，所以该算法的空间复杂度也是O（n）

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/152427.html

赞 (0)
老牧童老牧童
0
上一篇 2024-11-26 17:00
下一篇 2024-11-26 17:15

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信