文章目录

一、问题描述

【问题描述】

从标准输入中读入一个整数算术运算表达式，如5 - 1 * 2 * 3 + 12 / 2 / 2 =。计算表达式结果，并输出。

要求：

1、表达式运算符只有+、-、*、/，表达式末尾的’=’字符表示表达式输入结束，表达式中可能会出现空格；

2、表达式中不含圆括号，不会出现错误的表达式；

3、出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。

【输入形式】

在控制台中输入一个以’=’结尾的整数算术运算表达式。

【输出形式】

向控制台输出计算结果（为整数）。

【样例1输入】

5 - 1 * 2 * 3 + 12 / 2 / 2 =

【样例1输出】

2

二、AC代码

有点长

#include <stdio.h># define maxsize 1000typedef struct {int flag;//如果取1表示这个元素是整数，如果取0表示这个元素是运算符int num;char c;int level;}opts;// 初始化堆栈void initStack(int Top){Top=-1;}// 测试堆栈是否为空int isEmpty(int *Top){return *Top==0;//这里取0是因为我一开始把一个无关符号‘#’给压进去了，作为优先级最低的运算符，所以符号栈的栈底一直是这个无效符号}// 测试堆栈是否已满int isFull(int *Top){return *Top==maxsize-1;}// 进栈void push(opts s[],opts item,int *Top){if(isFull(&Top)){printf("the stack is full\n");return ;}else{s[++(*Top)]=item;}}// 出栈opts pop(opts s[],int *Top){if(isEmpty(&Top)){printf("the stack is empty\n");}elsereturn s[(*Top)--];}// 中缀表达式opts med[maxsize];// 后缀表达式opts post[maxsize];//整个表达式的长度int len;//运算符栈opts op[maxsize];int Top_op=-1;// 数字栈int num[maxsize];int Top_num=-1;//注意，这个Top_XX是栈顶元素的下标，取-1时表示该栈为空int i;int main(){int a;char c;//输入while(1){scanf("%d %c",&a,&c);med[len].flag=1;med[len].num=a;len++;if(c=='=')break;med[len].flag=0;med[len].c=c;if(c=='*'||c=='/')med[len].level=2;if(c=='+'||c=='-')med[len].level=1;len++;}initStack(Top_num);initStack(Top_op);op[0].flag=0,op[0].level=0;//在符号栈中加入‘#’Top_op++;int j=0,k=0,l=0;//j是运算符栈,k是运算数栈,l是后缀表达式//开始中缀转后缀for(i=0;i<len;i++){if(med[i].flag==1){post[l++]=med[i];}if(med[i].flag==0){if(med[i].level>op[Top_op].level){push(op,med[i],&Top_op);}else{while (med[i].level<=op[Top_op].level){post[l++]=pop(op,&Top_op);}push(op,med[i],&Top_op);}}}//把符号栈中剩余的符号弹到后缀式中while (!isEmpty(&Top_op)){post[l++]=pop(op,&Top_op);}/* 打印后缀式for(i=0;i<len;i++){if(post[i].flag)printf("%d ",post[i].num);elseprintf("%c ",post[i].c);}*/int num1=0,num2=0;for(i=0;i<len;i++){// printf("i=%d,Top_num=%d\n",i,Top_num);if(post[i].flag){num[++Top_num]=post[i].num;// printf("Top_num=%d\n",Top_num);}else{switch(post[i].c){case '+':num2=num[Top_num--];num1=num[Top_num--];num[++Top_num]=num1+num2;break;case '-':num2=num[Top_num--];num1=num[Top_num--];num[++Top_num]=num1-num2;break;case '*':num2=num[Top_num--];num1=num[Top_num--];num[++Top_num]=num1*num2;break;case '/':num2=num[Top_num--];num1=num[Top_num--];num[++Top_num]=num1/num2;break;}}}printf("%d\n",num[0]);}

三、注意点

这里就是提一下我一开始的错误，就是以为Top_XX是栈的长度，其实应该是栈顶元素的下标。

主要的注意事项主要分两部分，入栈和出栈

1）入栈：

入栈有3个条件

i）栈为空

ii）栈顶元素为左括号(

iii）栈顶运算符的优先级小于当前读入的运算符优先级，且当前运算符不是右括号)

2）出栈：

出栈有两种情况，读到了右括号需要出栈，优先级小于等于栈顶运算符优先级，但是不管怎么样都要满足栈不为空

i）如果读到了右括号：

在while循环中：保证栈顶元素不为左括号，一直到栈顶元素为左括号为止；

结束while循环后：并且while循环结束后还要把左括号弹出

ii）如果读到了非右括号：

在while循环中：保证(栈不为空&&栈顶元素不是左括号&&栈顶元素优先级大于等于当前运算符优先级)

结束while循环后:把当前运算符压入运算符栈中

四、实现思路/代码解析

1.主要的数据结构如下：

typedef struct {int flag;//如果取1表示这个元素是整数，如果取0表示这个元素是运算符int num;char c;int level;}opts;// 中缀表达式opts med[maxsize];// 后缀表达式opts post[maxsize];int len;//运算符栈opts op[maxsize];int Top_op=-1;// 数字栈int num[maxsize];int Top_num=-1;//注意，这个Top_XX是栈顶元素的下标，取-1时表示该栈为空

就是定义了一个结构体opt，存储运算数或者运算符，这个结构体有一个属性flag，判断这个结构体是数还是运算符，如果是运算符，那这个结构体还会有一个属性level，存储它的优先级用两个opt数组med[maxsize],post[maxsize]，一个存储中缀表达式，一个存储后缀表达式再用一个opt数组op[maxsize]+整型变量Top_op，作为运算符栈和运算符栈的栈顶下标；这个栈是在中缀转后缀时起作用的最后是整型数组num[maxsize]和整型变量Top_num，作为运算数栈和运算数栈的下标，这个栈是在计算后缀表达式的值时起作用的总之就是，运算符栈op[maxsize]只在中缀转后缀时起效，运算数栈num[maxsize]只在计算后缀表达式时起作用

2.具体中缀转后缀的思路可以参考我的另一篇文章：中缀后缀表达式的转换