1、以字符序列的形式从终端输入语法正确、不含变量的整数表达式。分成中缀表达式的输入和后缀表达式的输入两种。
2、利用给定的算符优先关系,分别对输入的中缀和后缀表达式实现其算术四则混合运算的求值,并演示在求值过程中的运算符栈、操作数栈、输入字符和主要操作的变化过程
中缀表达式的求值
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
char op[8]={'+','-','*','/','(',')','#'};
struct stsq
{
char *st;
int top;
int maxsize;
};
void initst(stsq &s,int ms)//构造堆栈
{
if(ms<=0){printf("ms is error!\n");exit(1);}
s.maxsize=ms;
s.st=new char[ms];
if(!s.st){printf("memory allocation failure!\n");}
s.top=-1;
}
void push(stsq &s,char item)//插入栈元素
{
if(s.top==s.maxsize-1){printf("st overflow!\n");exit(1);}
s.top++;
s.st[s.top]=item;
}
char gettop(stsq &s)//放入栈顶元素
{
if(s.top==-1){printf("st is empty!\n");exit(1);}
return s.st[s.top];
}
char pop(stsq &s)//删除栈元素
{
if(s.top==-1){printf("st is empty!\n");exit(1);}
s.top--;
return s.st[s.top+1];
}
int precedence1(char op)
{
switch(op)
{
case '+':case '-':return 2;break;
case '*':case '/':return 3;break;
case '#':return -1;break;
case '(':default:return 0;
}
}
int precedence2(char op)
{
switch(op)
{
case '+':case '-':return 1;break;
case '*':case '/':return 4;break;
case '#':case ')':return 0;break;
case '(':default:return 5;
}
}
char operate(char a,char tt,char b)
{
switch(tt)
{
case '+':return a+b-'0';break;
case '-':return a-b+'0';break;
case '*':return (a-'0')*(b-'0')+'0';break;
case '/':if(b!=0){return (a-'0')/(b-'0')+'0';}
else{printf("divide by 0!\n");exit(1);}break;
}
}
char precede(char a,char b)
{
int x,y;
x=precedence1(a);
y=precedence2(b);
if(x>y)return '>';
else if(x==y)return '=';
else return '<';
}
int in(char v,char*op)
{
int i=0;
while(i<7)
if(v==op[i++])return 1;
return 0;
}
int evaluateexpression()
{
stsq optr,opnd;
int y=25;
char v,tt,a,b,x;
initst(optr,y);push(optr,'#');
initst(opnd,y);v=getchar();
while(v!='#'||gettop(optr)!='#')
{
if(!in(v,op)){push(opnd,v);v=getchar();}
else
switch(precede(gettop(optr),v))
{
case'<':push(optr,v);v=getchar();break;
case'=':x=pop(optr);v=getchar();break;
case'>':tt=pop(optr);b=pop(opnd);a=pop(opnd);
push(opnd,operate(a,tt,b));
break;
}
}
return gettop(opnd);
}
void main()
{
printf("Please enter a expression and with # as a end:\n");
int wl=evaluateexpression();
printf("Reasult:%d\n",wl-'0');
}