一、实验目的
1.掌握栈的存储表示和实现
2.掌握栈的基本操作实现。
3.掌握栈在解决实际问题中的应用。
二、实验要求
问题描述：设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。
（1）输入的形式：表达式，例如2*(3+4)#
包含的运算符只能有’+’ 、’-’ 、’’ 、’/’ 、’(’、 ‘)’，“#”代表输入结束符；
（2）输出的形式：运算结果，例如2(3+4)=14；
（3）程序所能达到的功能：对表达式求值并输出。
三、解题参考思路
为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈opter，以及用于存储操作数及中间结果的栈opnd。
算法基本思想如下：
（1）首先将操作数栈opnd设为空栈，而将’#‘作为运算符栈opter的栈底元素，这样的目的是判断表达式是否求值完毕。
（2）依次读入表达式的每个字，表达式须以’#‘结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：
(i)若top的优先级小于c，即top
(ii)若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;
（iii）若top优先级高于c，即top>c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’，此时求值结束。
算符间的优先关系如下表所示（表来源：严蔚敏《数据结构》）：
表中需要注意的是θ1为opter的栈顶元素，θ2为从表达式中读取的操作符，此优先级表可以用二维数组实现。
图例：
比较算符优先关系代码示例：
int getIndex(char theta) //获取theta所对应的索引 { int index = 0; switch (theta) { case ‘+’: index = 0; break; case ‘-’: index = 1; break; case ‘*’: index = 2; break; case ‘/’: index = 3; break; case ‘(’: index = 4; break; case ‘)’: index = 5; break; case ‘#’: index = 6; default:break; } return index; } char getPriority(char theta1, char theta2) //获取theta1与theta2之间的优先级 { const char priority[][7] = //算符间的优先级关系 { { ‘>’,’>’,’<’,’<’,’<’,’>’,’>’ }, { ‘>’,’>’,’<’,’<’,’<’,’>’,’>’ }, { ‘>’,’>’,’>’,’>’,’<’,’>’,’>’ }, { ‘>’,’>’,’>’,’>’,’<’,’>’,’>’ }, { ‘<’,’<’,’<’,’<’,’<’,’=’,‘0’ }, { ‘>’,’>’,’>’,’>’,‘0’,’>’,’>’ }, { ‘<’,’<’,’<’,’<’,’<’,‘0’,’=’ }, }; int index1 = getIndex(theta1); int index2 = getIndex(theta2); return priority[index1][index2]; } ———————————————— 版权声明：本文为CSDN博主「superlistboy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_51222650/article/details/117048535
四、实验任务
认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。
（已改）代码如下
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define MAXSIZE 100 // 存储空间初始分配量 typedef int Status; typedef struct { int data[MAXSIZE]; int top; // 用于栈顶指针 }opndStack; typedef struct { char data[MAXSIZE]; int top; // 用于栈顶指针 }opterStack; //==================================================================== int getIndex(char theta) //获取theta所对应的索引 { int index = 0; switch (theta) { case '+': index = 0; break; case '-': index = 1; break; case '*': index = 2; break; case '/': index = 3; break; case '(': index = 4; break; case ')': index = 5; break; case '#': index = 6; default:break; } return index; } //==================================================================== char getPriority(char theta1, char theta2) //获取theta1与theta2之间的优先级 { const char priority[][7] = //算符间的优先级关系 { { '>','>','<','<','<','>','>' }, { '>','>','<','<','<','>','>' }, { '>','>','>','>','<','>','>' }, { '>','>','>','>','<','>','>' }, { '<','<','<','<','<','=','0' }, { '>','>','>','>','0','>','>' }, { '<','<','<','<','<','0','=' }, }; int index1 = getIndex(theta1); int index2 = getIndex(theta2); return priority[index1][index2]; } //==================================================================== Status InitopndStack(opndStack *S)//建立opnd空栈 { S->top=-1; return OK; } Status InitopterStack(opterStack *S)//建立opter空栈 { S->top=-1; return OK; } //==================================================================== Status Pushnd(opndStack *S,int n)//入栈 { if(S->top== MAXSIZE-1) { return ERROR; } S->top++;// S->data[S->top]=n; return OK; } Status Pushter(opterStack *S,char n) { if(S->top== MAXSIZE-1) { return ERROR; } S->top++;// S->data[S->top]=n; return OK; } //========================================================= Status Popnd(opndStack *S,int *n)//出栈 并返回到 n 中 { if(S->top==-1) return ERROR; *n=S->data[S->top]; (S->top)--; return OK; } Status Popter(opterStack *S,char *n) { if(S->top==-1) return ERROR; *n=S->data[S->top]; S->top--; return OK; } //======================================================= signed int calculate(int x1,int x2,char c) { switch(c) { case '+': return (x1+x2); case '-': return (x1-x2); case '*': return (x1)*(x2); case '/': return (x1)/(x2); default: return 0; } return 0; } //====================================================== int isdigit(char c)//判断是否为操作数 { if(c<='9'&& c>='0') return 1; else return 0; } int ischar(char c)//判断是否为运算符 { switch(c) { case '+': case '-': case '*': case '/': case '(': case ')': case '#': return 1; default: return 0; } return 0; } //========================================================= void input(char s[]) //输入表达式 存入s[]数组中。 { char c; int i = 0; while(c!='#') { while((c=getchar())==' ');//跳过所有空格进行c的输入 s[i++]=c; } return ; } //========================================================== int calculateall() { char c,s[100]={0},k; int x1,x2,i=0; int n=0; opndStack opnd; opterStack opter; InitopndStack(&opnd); //空栈 InitopterStack(&opter); Pushter(&opter,'#'); input(s); while(s[i]!='\0') { c=s[i]; if(ischar(c)) { switch(getPriority(opter.data[opter.top],c)) { case '<': Pushter(&opter,c); break; case '=': Popter(&opter,&k);//k没有用处 用来满足函数关系而已 break; case '>': while(getPriority(opter.data[opter.top],c)=='>') { Popnd(&opnd,&x1); Popnd(&opnd,&x2); Popter(&opter,&k); x1=calculate(x2,x1,k); Pushnd(&opnd,x1); } if(getPriority(opter.data[opter.top],c)=='<') Pushter(&opter,c); else Popter(&opter,&k); break; default: printf("INPUT ERROR"); } } else { Pushnd(&opnd,c-'0'); } ++i; } Popnd(&opnd,&k); return k; } //========================================================= int main() { int k; k=calculateall(); printf("%d",k); return 0; }
当时自己写的版本（c++）
#include <iostream> using namespace std; #include <string> #define size2 10 #define size1 100 #define erro -1 typedef int iii; typedef struct { char *base; char *top; int size; } stack2; typedef struct { iii * base; iii* top; int size; } stack; void InitStack(stack2 &s)//初始化栈 { s.base=(char*)malloc (size1*sizeof(char)); if(!s.base) { printf("超出界限\n"); return; } else { s.top=s.base; s.size=size1; } } void InitStack(stack &s)//初始化栈 { s.base=(iii *)malloc (size1*sizeof(iii)); if(!s.base) { printf("超出界限\n"); return; } else { s.top=s.base; s.size=size1; } } void Insert(stack2 &s,char a) //插入元素 { if(s.top-s.base>=s.size) { s.base=(char *)realloc (s.base,(s.size+size1)*sizeof (char)); if(!s.base) { printf("超出界限\n"); return ; } } *s.top++=a; } void Insert2( stack &s,int a) { if(s.top-s.base>=s.size) { s.base=(iii *)realloc (s.base,(s.size+size1)*sizeof (iii)); if(!s.base) { printf("超出界限\n"); return ; } } *s.top++=a; } char Pop(stack2 &s )//删除栈顶元素，并返回栈顶元素 { if(s.top==s.base) { printf("栈为空\n"); return erro; } else { *--s.top; return * s.top; } } int Pop2(stack &s) { if(s.top==s.base) { printf("栈为空\n"); return erro;//没意义 } else { *--s.top; return * s.top; } } void View(stack &s) { for(int i=1; i<=(s.top-s.base); i++) { char k; k=*(s.top-i); cout<<k<<endl; } } char GetPop(stack2 &s) { if(s.top==s.base) { printf("栈为空\n"); return-1; } else return *(s.top-1); } int GetPop2(stack &s) { if(s.top==s.base) { printf("栈为空\n"); return-1; } else return *(s.top-1); } char Compare(char q,char r)//比较优先级 { int j[2]; char str[2]; char table[7][7]= { {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','e'}, {'>','>','>','>','e','>','>'}, {'<','<','<','<','<','e','='} }; str[0]=q; str[1]=r; for(int i=0; i<2; i++) { switch(str[i]) { case '+': j[i]=0; break; case '-': j[i]=1; break; case '*': j[i]=2; break; case '/': j[i]=3; break; case '(': j[i]=4; break; case ')': j[i]=5; break; case '#': j[i]=6; break; } } return table[j[0]][j[1]]; } int Operate (int a,char b,int c) { switch(b) { case '+': return a+c; case '-': return a-c; case '*': return a*c; case '/': return a/c; } } bool Decide(char c) { if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#') return true; else return false; } int main() { stack2 a; stack b;//a存储符号，b存储数字 InitStack(a); Insert(a,'#'); InitStack(b); char c; c=getchar(); int temp=0; while (c!='#'||GetPop(a)!='#') { if(!Decide(c)) { temp=(temp*10+c-'0');//可支持数位数字 c=getchar(); } else if(Decide(c)) { if(temp!=0) { Insert2(b,temp); } temp=0; switch(Compare(GetPop(a),c)) { case '<': //栈顶元素优先权低 //cout<<"<"<<endl; Insert(a,c); c=getchar(); break; case '=': //脱括号 Pop(a); c=getchar(); break; case'>': char f=Pop(a); int g=Pop2(b); int h=Pop2(b); Insert2(b,Operate(h,f,g)); break; } } } cout<<"结果为"<<endl; cout<<GetPop2(b)<<endl; return 0; }
