设计⼀个程序，演⽰⽤算符优先法对算术表达式求值的过程。利⽤算符优先关 系，实现对算术四则混合。。。
⼀、实验⽬的
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<c，则将c直接⼊栈opter，并读⼊下⼀字符赋值给c；
(ii)若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读⼊下⼀字符赋值给c，这⼀步⽬的是进⾏括号操作;
（iii）若top优先级⾼于c，即top>c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放⼊栈opnd中。直⾄opter的栈顶元素和当前读⼊的字符均为’#’，此时求值结束。
遵义市委书记廖少华算符间的优先关系如下表所⽰（表来源：严蔚敏《数据结构》）：
表中需要注意的是θ1为opter的栈顶元素，θ2为从表达式中读取的操作符，此优先级表可以⽤⼆维数组实现。
1.int getIndex(char theta)//获取theta所对应的索引
2.{
3.int index =0;
4.switch(theta)
5.{
6.case'+':
7. index =0;
8.break;
9.case'-':
10. index =1;
11.break;
12.case'*':
13. index =2;
14.break;
15.case'/':
16. index =3;
17.break;
18.case'(':
19. index =4;
20.break;
21.case')':
22. index =5;
23.break;
24.case'#':
25. index =6;
26.default:break;
27.}
29.}
30.
31.char getPriority(char theta1,char theta2)//获取theta1与theta2之间的优先级
32.{
34.{
高考之外35.{'>','>','<','<','<','>','>'},
36.{'>','>','<','<','<','>','>'},
37.{'>','>','>','>','<','>','>'},
38.{'>','>','>','>','<','>','>'},
39.{'<','<','<','<','<','=','0'},
40.{'>','>','>','>','0','>','>'},
41.{'<','<','<','<','<','0','='},
42.};
43.
44.int index1 =getIndex(theta1);
45.int index2 =getIndex(theta2);
}
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"math.h"
#define true 1
#define false 0
#define OPSETSIZE 8
typedef int Status;
int getIndex(char theta);
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];
}
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;
}
typedef struct StackChar
char c;//数据域
struct StackChar *next;//指针域
}SC;//StackChar类型的结点SC
typedef struct StackFloat
{//定义链表类型的数组，是⽤来存储运算数字的栈的
float f;//数据域
struct StackFloat *next;//指针域
}SF;//StackFloat类型的结点SF
SC *Push(SC *s,char c)//SC类型的指针Push，返回p {//压⼊元素
SC *p=(SC*)malloc(sizeof(SC));//分配⼀个SC类型的空间p p->c=c;//给p的数据域赋值
p->next=s;//把p的指针域指向s
return p;//返回最新的栈顶位置
}
SF *Push(SF *s,float f)//SF类型的指针Push，返回p {//压⼊元素
SF *p=(SF*)malloc(sizeof(SF));//分配⼀个SC类型的空间p p->f=f;//给p的数据域赋值
p->next=s;//把p的指针域指向s
return p;//返回最新的栈顶位置
}
SC *Pop(SC *s)//SC类型的指针Pop
{//⽤来将char类型的操作符栈的栈顶元素弹出栈
SC *q=s;//临时指针q⽤来临时保存栈顶元素的位置
s=s->next;//将s指针指向s后⾯的⼀个元素
free(q);
2012年广东高考语文作文return s;
}
SF *Pop(SF *s)//SF类型的指针Pop
{//⽤来将float类型的栈的栈顶元素(被运算的数字)弹出栈
SF *q=s;
s=s->next;
free(q);
return s;
}
float Operate(float a,unsigned char theta,float b)//计算函数Operate
{
switch(theta)
{
case'+':return a+b;
case'-':return a-b;
case'*':return a*b;
case'/':return a/b;
default:return0;
}
}
char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#'};
Status In(char Test,char*TestOp)
{//IN函数⽤来判定当前元素是否为运算符
int Find=false;
for(int i=0; i< OPSETSIZE; i++)
{
if(Test == TestOp[i])
Find=true;
}
return Find;//如果是运算符返回1(TURE)，否则返回0(FALSE)
}
Status ReturnOpOrd(char op,char*TestOp)
{
for(int i=0; i< OPSETSIZE; i++)
{
if(op == TestOp[i])
return i;
}
}
float EvaluateExpression(char* MyExpression)//将运算表达式(MyExpression)传⼊处理函数{
// 算术表达式求值的算符优先算法
// 设OPTR和OPND分别为运算符(operator)栈和运算数(operand)栈，OP为运算符集合
SC *OPTR=NULL;// 运算符栈，字符元素
SF *OPND=NULL;// 运算数栈，实数元素
char TempData[20];
float Data,a,b;
char theta,*c,Dr[]={'#','\0'};
OPTR=Push(OPTR,'#');//在运算符栈栈底压⼊"#"，当作结束标志位
c=strcat(MyExpression,Dr);//给运算表达式末尾添加Dr[]={'#','\0'}
strcpy(TempData,"\0");//字符串拷贝函数
while(*c!='#'|| OPTR->c!='#')//只要运算表达式c未循环到末尾(c指向不为末尾的"#")，或则OPTR栈未到栈底{
if(!In(*c, OPSET))//如果当c所指向的不是字符
{
Dr[0]=*c;
strcat(TempData,Dr);//字符串连接函数
c++;
if(In(*c, OPSET))
{
Data=atof(TempData);//atof(ascii to float)字符串转换函数(double)，把字符转化为double类型
OPND=Push(OPND, Data);//操作数压⼊
strcpy(TempData,"\0");
}
}
else// 不是运算符则进栈
{
谢旭人简历switch(getPriority(OPTR->c,*c))//判断当前操作数，和栈顶操作数的优先级⼤⼩
{
case'<':// 栈顶元素优先级低，当前元素直接进栈
OPTR=Push(OPTR,*c);
c++;
break;
case'=':// 脱括号并接收下⼀字符
OPTR=Pop(OPTR);
c++;
break;
case'>':// 退栈并将运算结果⼊栈,
theta=OPTR->c;OPTR=Pop(OPTR);
b=OPND->f;OPND=Pop(OPND);
a=OPND->f;OPND=Pop(OPND);
OPND=Push(OPND,Operate(a, theta, b));
break;
}//switch
}
电冰箱保护器
}//while
return OPND->f;
}//EvaluateExpression
int main(void)
{
char s[128];
puts("请输⼊表达式:");
gets(s);
puts("该表达式的值为:");
printf("%s\b=%g\n",s,EvaluateExpression(s));
system("pause");
return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议