数据结构中对于栈的运用，最主要的一个例子就是简单表达式的计算了，当你独自将这个程序写出来的时候，这说明你对于栈的运用已经炉火纯青了，下面我将对这个问题做出详细的解答，让我们一起来看看吧
【问题描述】
设计一个程序，实现简单整数的四则运算（运算对象不小于0），包括加减乘除和小括号。
【输入形式】
每行输入一个运算表达式（假设表达式均为正确的表达式），以#作为表达式结束。（表达式长度不超过80）
【输出形式】
输出表达式的后缀式
输出运算结果
【样例输入】
23-(2-4)*2+36/(20-14)#
(100-23)/6+2*(13-9)-40#
((100-20)*2)-35#
120+30+50#
【样例输出】
23 2 4 - 2 * - 36 20 14 - / +
33
100 23 - 6 / 2 13 9 - * + 40 -
-20
100 20 - 2 * 35 -
125
120 30 + 50 +
200
目录
方法一
在方法一中呢我们定义两个主要函数，再在主函数中使用两个函数，最终求出表达式的值
一个函数用来求出原式子的后缀式
另一个函数用来进行后缀式的计算
1.1 后缀式的转换
后缀式的转换是个老生常谈的问题了，对于这个问题一定不能忘了要先设置运算符的优先级
int f(char s){ //我们需要先设置运算符的优先级
if(s=='#') return -1;
else if(s=='('||s==')') return 0;
else if(s=='+'||s=='-') return 1;
else if(s=='*'||s=='/') return 2;
}
int Change(char *s1,char *s2){
int i=0,e;
PStack S;
S=Init_Stack();
Push_Stack(S,'#'); //初始化栈，置栈底为#
while(*s1!='#'){ //因为输入#结束，所以最后一个输入的字符是#,当遇到#终止循环
if(*s1>='0'&&*s1<='9'){ //遇到非运算符的时候
while(*s1>='0'&&*s1<='9'){ //当有连续的非运算符，我们需要把他们放到一起
s2[i++]=*s1;
s1++;
}
s2[i++]=' '; //用空格将
不同元素隔开，方便后缀式的计算
s1--; //这里的s1--千万不能少！！
}else{ //当遇到运算符时
Get_Stack(S,&e); //获取栈顶元素
if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){ //如果优先级大于栈顶元素且不是")"
Push_Stack(S,*s1); //或者遇到了"("，直接入栈
}else if(*s1==')'){ //如果读取的字符是")"，先出栈，再判断
Pop_Stack(S,&e);
while(e!='('){ //遇到非"("的运算符放入后缀式
s2[i++]=e; //遇到"("出栈后不用放到后缀式
s2[i++]=' ';
Pop_Stack(S,&e);
}
}else{ //当运算符优先级小于栈顶元素时，出栈放入后缀式直到大于栈顶元素
while(f(*s1)<=f(e)){
Pop_Stack(S,&e);
s2[i++]=e;
s2[i++]=' ';
Get_Stack(S,&e);
}
Push_Stack(S,*s1); //入栈
}
}
s1++;
}
while(!Empty_Stack(S)){ //将栈中剩余运算符都放入后缀式
Pop_Stack(S,&e);
s2[i++]=e;
}
int k=0;
while(1){
if(s2[k]=='#') break;
printf("%c",s2[k++]); //打印后缀式
}
printf("\n");
return 1;
}1.2 计算后缀式
计算后缀式的方法是遍历后缀式，每遇到数字字符入栈，遇到运算符时从栈中取两个元素，进行计算，将计算结果放入栈中，用于下一次计算
int Match(char *s){
int a,b,x;
PStack S;
S=Init_Stack(); //初始化一个栈
while(*s!='\0'){ //循环
if(*s>='0'&&*s<='9'){ //当遇到数字字符时
x=0;
while(*s>='0'&&*s<='9'){ //使用此方法将字符串转换成整型变量，用于计算
x=*s-'0'+x*10;
s++;
}
Push_Stack(S,x); //入栈
}else if(*s!=' '){ //当遇到非空格且不是数字字符时
Pop_Stack(S,&a); //出栈一个数字
Pop_Stack(S,&b); //再出栈一个数字
switch(*s){ //进行运算，将运算结果放入栈中
case '+':x=a+b;break;
case '-':x=b-a;break;
case '*':x=a*b;break;
case '/':x=b/a;break;
}
Push_Stack(S,x);
}
s++;
}
Pop_Stack(S,&x); //最后出栈，打印最后一个元素即是表达式的解
printf("%d",x);
return 1;
}1.3 完整代码
#include<stdio.h>
#include<malloc.h>
typedef struct Stack{
int data;
struct Stack * next;
}Stack,*PStack;
PStack Init_Stack(){
PStack S=(PStack)malloc(sizeof(Stack));
S->next=NULL;
return S;
}
int Empty_Stack(PStack S){
if(!S->next) return 1;
else return 0;
}
int Push_Stack(PStack S,int e){
PStack P=(PStack)malloc(sizeof(Stack));
P->data=e;
P->next=NULL;
P->next=S->next;
S->next=P;
return 1;
}
int Pop_Stack(PStack S,int *e){
if(!S->next) return 0;
*e=S->next->data;
S->next=S->next->next;
return 1;
}
int Get_Stack(PStack S,int *e){
if(!S->next) return 0;
*e=S->next->data;
return 1;
}
int f(char s){
if(s=='#') return -1;
else if(s=='('||s==')') return 0;
else if(s=='+'||s=='-') return 1;
else if(s=='*'||s=='/') return 2;
}
int Change(char *s1,char *s2){
int i=0,e;
PStack S;
S=Init_Stack();
Push_Stack(S,'#');
while(*s1!='#'){
if(*s1>='0'&&*s1<='9'){
while(*s1>='0'&&*s1<='9'){
s2[i++]=*s1;
s1++;
}
s2[i++]=' ';
s1--;
}else{
Get_Stack(S,&e);
if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){
Push_Stack(S,*s1);
}else if(*s1==')'){
Pop_Stack(S,&e);
while(e!='('){
s2[i++]=e;
s2[i++]=' ';
Pop_Stack(S,&e);
}
}else{
while(f(*s1)<=f(e)){
Pop_Stack(S,&e);
s2[i++]=e;
s2[i++]=' ';
Get_Stack(S,&e);
}
Push_Stack(S,*s1);
}
}
s1++;
}
while(!Empty_Stack(S)){
Pop_Stack(S,&e);
s2[i++]=e;
}
int k=0;
while(1){
if(s2[k]=='#') break;
printf("%c",s2[k++]);
}
printf("\n");
return 1;
}
int Match(char *s){
int a,b,x;
PStack S;
S=Init_Stack();
while(*s!='\0'){
if(*s>='0'&&*s<='9'){
x=0;
while(*s>='0'&&*s<='9'){
x=*s-'0'+x*10;
s++;
}
Push_Stack(S,x);
}else if(*s!=' '){
Pop_Stack(S,&a);
Pop_Stack(S,&b);
switch(*s){
case '+':x=a+b;break;
case '-':x=b-a;break;
case '*':x=a*b;break;
case '/':x=b/a;break;
}
Push_Stack(S,x);
}
s++;
}
Pop_Stack(S,&x);
printf("%d",x);
return 1;
}
int main(){
char s1[100],s2[100];
scanf("%s",s1);
Change(s1,s2);
Match(s2);
return 0;
}方法二
在方法二中我们只定义了一个计算函数，然后在主函数中边转换后缀式边进行计算（这样大大提高了计算效率）
1.1 计算函数
我们设计一个计算函数，用于后缀式的计算
int match(SqStack *s,char s2) //函数需要两个参量
{ //一个是栈，另一个是字符
int a,b;
ElemType e;
switch(s2) //定义每一种字符的运算规则
{
case '+':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a+b);
break;
case '-':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a-b);
break;
case '*':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a*b);
break;
case '/':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a/b);
break;
case '#':break;
}
}1.2 主函数
在主函数中，我们边进行后缀式转换，边进行表达式的计算，大大节省了程序运行的时间
int main()
{
char s[100];
while(gets(s))
{
SqStack s1,s2;
InitStack(&s1); //第一个栈用于转换后缀式
InitStack(&s2); //第二个栈用于计算后缀式
Push(&s1,'#');
int i;
for(i=0;i<strlen(s);i++)
{
if(s[i]==')')
{
ElemType e;
while(GetTop(&s1,&e)&&e!='(')
{
printf("%c ",e); //遇到字符进行运算
match(&s2,e);
Pop(&s1,&e); //取出这个字符
}
Pop(&s1,&e); //遇到"("时取出就好
}
else if(s[i]>='0'&&s[i]<='9') //遇到数字时
{
int x=0;
while(s[i]>='0'&&s[i]<='9') //先将数字转换为整型
{
x=x*10+(s[i]-'0');
i++;
}
Push(&s2,x); //将整型变量放入栈中，用于运算
printf("%d ",x);
i--;
}
else
{
ElemType e;
if(s[i]!='(') //当你遇到的字符不是"("
{
while(GetTop(&s1,&e)&&f(s[i])<=f(e)) //且运算符优先级小于栈顶元素
{
if(e!='#')printf("%c ",e);
match(&s2,e); //执行运算
Pop(&s1,&e); //取出栈顶元素，继续下一次判断
}
}
Push(&s1,s[i]); //直到优先级大于栈顶元素，入栈
}
}
int m;
GetTop(&s2,&m); //栈中最后只剩栈底元素"#"和最后一个值，最后一个值就是表达式结果
printf("\n%d",m);
}
return ERROR;
}1.3 完整代码
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode,*SqStack;
int InitStack(SqStack *s)
{
(*s)=NULL;
return OK;
}
int EmptyStack(SqStack *s)
{
if(*s==NULL) return OK;
else return ERROR;
}
int Push(SqStack *s,ElemType e)
{
SqStack p;
p=(SqStack)malloc(sizeof(StackNode));
p->data=e;
p->next=*s;
*s=p;
return OK;
}
int Pop(SqStack *s,ElemType *e)
{
if(*s==NULL)
return ERROR;
else
{
SqStack p;
p=*s;
*e=p->data;
*s=(*s)->next;
free(p);
return OK;
}
}
int GetTop(SqStack *s,ElemType *e)
{
if(*s==NULL)
return ERROR;
else
{
*e=(*s)->data;
return OK;
}
}
int f(char s2)
{
if(s2=='#') return -1;
else if(s2=='(') return 0;
else if(s2=='+'||s2=='-') return 1;
else if(s2=='*'||s2=='/') return 2;
}
int match(SqStack *s,char s2)
{
int a,b;
ElemType e;
switch(s2)
{
case '+':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a+b);
break;
case '-':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a-b);
break;
case '*':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a*b);
break;
case '/':
GetTop(s,&b);
Pop(s,&e);
GetTop(s,&a);
Pop(s,&e);
Push(s,a/b);
break;
case '#':break;
}
}
int main()
{
char s[100];
while(gets(s))
{
SqStack s1,s2;
InitStack(&s1);
InitStack(&s2);
Push(&s1,'#');
int i;
for(i=0;i<strlen(s);i++)
{
if(s[i]==')')
{
ElemType e;
while(GetTop(&s1,&e)&&e!='(')
{
printf("%c ",e);
match(&s2,e);
Pop(&s1,&e);
}
Pop(&s1,&e);
}
else if(s[i]>='0'&&s[i]<='9')
{
int x=0;
while(s[i]>='0'&&s[i]<='9')
{
x=x*10+(s[i]-'0');
i++;
}
Push(&s2,x);
printf("%d ",x);
i--;
}
else
{
ElemType e;
if(s[i]!='(')
{
while(GetTop(&s1,&e)&&f(s[i])<=f(e))
{
if(e!='#')printf("%c ",e);
match(&s2,e);
Pop(&s1,&e);
}
}
Push(&s1,s[i]);
}
}
int m;
GetTop(&s2,&m);
printf("\n%d",m);
}
return ERROR;
}运行结果
本文含有隐藏内容，请 开通VIP 后查看