算术表达式求值演⽰算术表达式求值演⽰
2.5⑤ 算术表达式求值演⽰
【问题描述】
表达式计算是实现程序设计语⾔的基本问题之⼀，也是栈的应⽤的⼀个典型例⼦。设
计⼀个程序，演⽰⽤算符优先法对算术表达式求值的过程。
【基本要求】
以字符序列的形式从终端输⼊语法正确的、不含变量的整数表达式。利⽤教科书表
3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3-1演⽰在求值中运算符栈、运算数栈、输⼊字符和主要操作的变化过程。
【测试数据】
教科书例 3-1 的算术表达式 3* （7-2），以及下列表达式
8;
1+2+3+4;
88-1×5;
1024/4×8;
1024/（4×8）;
(20+2）×（6/2）;
3-3-3;
8/(9-9);
2×(6+2×（3+6×（6+6）））;
（（(6+6）×6+3)×2+6）×2;
【实现提⽰】
（1）设置运算符栈和运算数栈辅助分析算符优先关系。
（2）在读⼊表达式的字符序列的同时，完成运算符和运算数(整数)的识别处理，以及
相应的运算。
（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。
（4）在程序的适当位置输出运算符栈、运算数栈、输⼊字符和主要操作的内容。
【选作内容】
（1）扩充运算符集，如增加乘⽅、单⽬减、赋值等运算。
（2）运算量可以是变量。
（3）运算量可以是实数类型。
（4）计算器的功能和仿真界⾯。
源代码
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define STACKINCREMENT 5
#define STACK_INIT_SIZE 10
typedef char SElemType;
typedef int Status;
typedef struct{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//当前已经分配的存储空间
}SqStack;
char prior[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','!'},{'>','>','>','>','!','>','>'},
{'<','<','<','<','<','!','='}};//定义算符之间优先关系的⼆维数组
//构造⼀个存放char型数据的空栈
Status InitStack(SqStack *s){
s->base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s->base)return ERROR;
s->top = s->base;//栈中元素个数为0
s->top = s->base;//栈中元素个数为0
s->stacksize = STACK_INIT_SIZE;
return OK;
}
//⼊栈
Status Push(SqStack *s,SElemType e){
if(s->top-s->base>=s->stacksize){
s->base =(SElemType *)realloc(s->base,(STACKINCREMENT+s->stacksize)*sizeof(SElemType));
if(!s->base)exit(0);
s->top = s->base+s->stacksize;
s->stacksize += STACKINCREMENT;
}
*s->top++= e;
return OK;
}
//出栈
Status Pop(SqStack *s,SElemType *e){
if(s->base==s->top){
printf("空栈！\n");
return ERROR;
}
*e =*--s->top;
return OK;
}
//得到栈顶元素
SElemType GetTop(SqStack *s){
return*(s->top-1);
}
//确定输⼊的字符如果是操作符的话判断在⼆维数组中的下标若是数字的话就另外与操作符区分开便于在输⼊表达式时是⼊哪个栈int Index(char c){
switch(c){
case'+':return0;
case'-':return1;
case'*':return2;
case'/':return3;
case'(':return4;
case')':return5;
case'#':return6;
default:return7;
}
}
//判断优先级，返回⼤⼩ < > = !
char Priority(char a,char b){
int x,y;
x =Index(a); y =Index(b);
if(x!=7&&y!=7)
return prior[x][y];
else
return'!';
}
//简单表达式求值
int Reckon(int a,char theta,int b){
switch(theta){
case'+':return a+b;
case'-':return a-b;
case'*':return a*b;
case'/':return a/b;
}
}
/
/判断是字符是否是数字
Status isdigit(char ch){
if(ch>='0'&&ch<='9')return OK;
return ERROR;
}
//算术表达式求值
Status PrintStack1(SqStack S,int&m)
Status PrintStack1(SqStack S,int&m)
//若栈S不空 则从栈底到栈顶输出S的元素(为char型)并返回打印长度
{
m=0;
char*p;
if(S.base==S.top)return ERROR;
for(p=S.base;p!=S.top;p++)
{printf("'%c'",*p); m++;}
return OK;
}//PrintStack1
Status PrintStack2(SqStack S,int&n)
//若栈S不空 则从栈底到栈顶输出S的元素(为char型)并返回打印长度
{
n=0;
char*p;
if(S.base==S.top)return ERROR;
for(p=S.base;p!=S.top;p++)
{printf("'%d'",*p); n++;}
return OK;
}//PrintStack1
void GetExpressionValue(){
int m,n,i=0;
SqStack OPTR,OPND;
SElemType result;//返回最后结果
switch case判断字符串InitStack(&OPTR);
InitStack(&OPND);
Push(&OPTR,'#');//将结束符置于操作符的底端
printf("请输⼊算术表达式(以#结尾）:\n");
char c =getchar();
printf("步骤\tOPTR栈\t\tOPND栈\t\t当前字符主要操作\n");
while(c!='#'||GetTop(&OPTR)!='#'){//当*c=='#'&&栈顶字符=='#'的时候
i++;
printf("  %d\t",i);//打印序号
PrintStack1(OPTR,m);putchar('\t');//打印OPTR栈
if(m<8)putchar('\t');//若打印长度不够8 要再
PrintStack2(OPND,n);putchar('\t');//打印OPND栈
if(n<8)putchar('\t');
if(isdigit(c)){//如果是数字的话将其转化为数字然后⼊操作数栈
int data[10];
int i,num;
i = num =0;//num是⼀个中间数⽤于将字符串中的数字转化为整数然后⼊栈 i是⽤于将字符串中的字符存⼊data数组while(isdigit(c)){
data[i]= c-'0';
i++;
c =getchar();
}
for(int j=0;j<i;j++){
num = num*10+data[j];
}
printf("  %d\t  ",num);//打印当前字符
printf("Push2(OPND,%d)\n",num);//打印该操作
Push(&OPND,num);
}else{//如果是字符的话将其⼊操作符栈
SElemType a,b,theta;//a b theta是⽤来返回操作数栈和操作符栈⾥的元素的
switch(Priority(GetTop(&OPTR),c)){//⽐较即将⼊栈的字符与栈顶操作符的优先级关系
case'<':Push(&OPTR,c);
printf("  %c\t  ",c);//打印当前字符
printf("Push1(OPND,%c)\n",c);//打印该操作
c =getchar();
break;
case'>':Pop(&OPND,&b);
Pop(&OPND,&a);
Pop(&OPTR,&theta);
Pop(&OPTR,&theta);
Push(&OPND,Reckon(a,theta,b));
printf("  %c\t  ",c);//打印当前字符
printf("Operate(%d,'%c',%d)\n",a,theta,b);//打印该操作break;//将结果⼊栈
case'=':Pop(&OPTR,&theta);
c =getchar();
break;//说明括号相遇删除栈内括号即可
default:break;
}
}
}
Pop(&OPND,&result);
printf("结果是：%d",result);
}
void main(){
GetExpressionValue();
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。