C语言：中缀算术表达式求值（栈附答案）.docx

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.03M 资料格式：docx 举报版权申诉

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第1页.png

第1页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第2页.png

第2页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第3页.png

第3页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第4页.png

第4页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第5页.png

第5页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第6页.png

第6页 / 共7页

714211bc-aca8-432f-a47d-f12cc59055cd.docx.pdf-第7页.png

第7页 / 共7页

中缀算术表达式求值

题目

算法

代码实现

中缀算术表达式求值题目输入一个中缀算术表达式，计算其结果。对输入的表达式，做如下假设：（1）只考虑+、-、*、/这四种运算符，中缀表达式中只有一种括号（）；（2）输入的中缀表达式中数字只有整数，没有小数；（3）假定输入表达式是合法的。算法基本思路：设置两个工作栈，都为链栈，一个存储操作数，一个存储运算符。然后输入想要求解的表达式，表达式不正确则需要重新输入，最后输出结果主要的两个工作函数的基本算法 1. compare()函数 1）遍历输入的字符串 y[] 2）当遇到操作数时，操作数进操作数栈 3）当遇到运算符时，判断其是否为（，是则进入 4），不是则进入 5） 4）如果后面跟的是操作数或者是（都入栈，直到遇到第一个非（的运算符将其压入运算符栈 5）当该运算符是否为) 且栈顶元素为（两者满足将栈顶元素（弹出 6）取出该运算符的标志位，与栈顶元素的标志位比较，若该运算符的标志位大则该运算符进栈，否则进行 yunsuan()操作，直到该运算符为#且栈顶元素为#时，将结果输出 2. yunsuan()函数从操作数栈中弹出两个量 n1,n2，从运算符栈中弹出一个量 op，通过判断 op 是四则运算中的哪个将 n1 和 n2 进行运算，并将运算结果压入操作数栈中注意：这里运算符的优先级别是这样规定的* / 3 + - 2 ) 1 # 0

没有给（进行优先级别的运算，而是遇到（直接将其压入栈内，并将第一个不为（的字符（包括该字符）都压入栈内代码实现 #include #include #include #include #define SIZE1 sizeof(struct stack1) #define SIZE2 sizeof(struct stack2) //进行重新设计，需要两个不同的记录来封装数据 struct stack1*base1,*top1; struct stack2*base2,*top2;//用于建立 int 栈 struct stack1 { int flag;//用于保存优先级 char data;//保存者运算符的变量 struct stack1*next;//提供链接 }; struct stack2 { int number; struct stack2*next; }; struct stack1 *init_stack1()//初始化栈 { struct stack1 *head;//定义栈顶指针 head=(struct stack1*)malloc(SIZE1);//让栈顶指针指向新创建的结点 head->next=NULL; return head;//返回栈的头部 } struct stack2 *init_stack2()//初始化栈 { struct stack2 *head;//定义栈顶指针 head=(struct stack2*)malloc(SIZE2);//让栈顶指针指向新创建的结点 head->next=NULL; return head;//返回栈的头部

} int change(char x) { //用于得出每个运算符的优先级便于进行比较 int flag; switch(x) { } case'#':flag=0;break; case')':flag=1;break; case'+': case'-':flag=2;break; case'*': case'/':flag=3;break; case'(':flag=4;break; return flag; } void push_op(struct stack1 *head,char x) { //让操作符入栈 //当栈空时，直接插入结点，当栈不为空时，在当前栈顶的前面插入一个结点 struct stack1*p; if(head->next==NULL) { p=malloc(SIZE1); p->data=x; p->flag=change(x); printf("%c 已经入栈！\n",x); head->next=p; top1=base1=p; } else//栈不为空 { //在前面插入结点 p=malloc(SIZE1); p->data=x; p->flag=change(x); head->next=p; p->next=top1; top1=p; printf("%c 已经入栈！\n",x); } }

void push_sz(struct stack2 *head,int x) { //让操作符入栈 //当栈空时，直接插入结点，当栈不为空时，在当前栈顶的前面插入一个结点 struct stack2*p; if(head->next==NULL) { p=malloc(SIZE2); p->number=x; printf("%d 已经入栈！\n",x); head->next=p; top2=base2=p; } else//栈不为空 { //在前面插入结点 p=malloc(SIZE2); p->number=x; head->next=p; p->next=top2; top2=p; printf("%d 已经入栈！\n",x); } } char pop1(struct stack1*head) { //将运算符栈顶元素弹出 struct stack1*p; char a; p=top1; a=p->data; head->next=top1->next;//弹出结点 top1=top1->next; free(p); printf("%c 已经从栈中取出！\n",a); return a; } int pop2(struct stack2*head) { //将操作数栈顶元素弹出 struct stack2*p; int a; p=top2; a=p->number;

head->next=top2->next;//弹出结点 top2=top2->next; free(p); printf("%d 已经从栈中取出！\n",a); return a; } void yunsuan(struct stack1*stack_1,struct stack2*stack_2) { //该函数用于进行操作数和运算符的运算 char op; int n1=0,n2=0,result=0; op=pop1(stack_1);//取出运算符 n1=pop2(stack_2);//取出操作数 n2=pop2(stack_2); switch(op) { case'+':result=n1+n2;break; case'-':result=n2-n1;break; case'*':result=n1*n2;break; case'/':result=n2/n1;break; } push_sz(stack_2,result); } int compare(char y[],int number,struct stack1*stack_1,struct stack2*stack_2) { //实现主要的比较操作 int i,j,k;//j 用于保存运算符的优先级 int result; char a[2]; for(i=0;i=48)//说明是字符串中的数字，转换为 int 压入操作数栈 { a[0]=y[i]; a[1]='\0'; k=atoi(a); push_sz(stack_2,k);//入操作符栈 } else//入运算符栈 { if(y[i]=='(')//无需比较将其入栈且下一个运算符也直接入栈 { //实现多括号的运算 push_op(stack_1,y[i]);

i++;//往下走 for(;;i++) { if(y[i]>=48) { a[0]=y[i]; a[1]='\0'; k=atoi(a); push_sz(stack_2,k);//入操作符栈 } else { if(y[i]=='(') push_op(stack_1,y[i]); else { push_op(stack_1,y[i]); break; } } } } else//需要与运算符栈顶元素进行优先级的比较 { j=change(y[i]);//将优先级带出来 if(j==0&&stack_1->next->flag==0)//说明运算结束直接将操作数栈的栈顶元素弹出 result=pop2(stack_2); break; { } else { if(y[i]==')'&&top1->data=='(')//当两个括号相遇时将其消去 pop1(stack_1); else { if(j>stack_1->next->flag)//优先级高则直接入栈 push_op(stack_1,y[i]); else//优先级小与或者等于栈顶元素时，进行运算 { yunsuan(stack_1,stack_2); i--; }

} } } } } return result; } int main() { struct stack1*stack_1; struct stack2*stack_2; stack_1=init_stack1();//操作数栈的初始化 stack_2=init_stack2();//运算栈的初始化 char x; int num,result=0; x='#'; char y[50]; push_op(stack_1,x); printf("请输入想要计算的表达式（注意括号要用英文括号！）：\n"); printf("请用#结尾\n"); gets(y); while(1)//用于控制正确输入 { num = strlen(y); if(y[num-1]=='#') break; else { } printf("输入不规范！请重新输入：\n"); gets(y); } result=compare(y,num,stack_1,stack_2); printf("最后结果为：%d",result); return 0; }

分享到：

赞收藏

资料库

C语言：中缀算术表达式求值（栈附答案）.docx

相关推荐

课程资源

热门标签

最新资料