应用sqstack,用算符优先算法,计算中缀表达式的值。
【输入形式】1行:以#号结束的中缀表达式;
【输出形式】1行:输出计算结果;
【样例输入】(4+2)*3-6/2#
【样例输出】15
【样例说明】空串输出0
【样例范围】对于100%的操作数0<=a<=9,表达式均没有语法错误,且运算符只有+、-、*、/、(、)。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define overflow -2
#define error 0
#define ok 1
#define stack_init_size 100
#define stackincrement 10
typedef int status;
typedef char selemtype;
typedef struct
{
selemtype *base;
selemtype *top;
int stacksize;
}sqstack;
//sqstack的4个函数:
status initstack(sqstack &s) //初始化栈
{ s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype));
if (!s.base) return error;
s.top=s.base;
s.stacksize=stack_init_size;
return ok;
}
status inputstack(sqstack &s)//输入栈
{ int i,n;
//printf("please input the length of the sqstack:");
scanf("%d",&n);
//printf("please input the data of the sqstack:");
for (i=1;i<=n;i++)
{
scanf("%d",s.top);
s.top++;
}
return ok;
}
status stacktraverse(sqstack s)//输出栈,先输出长度,后输出元素
{
int i;
printf("the length of the stack:%d\n",s.top-s.base);
printf("the data of the stack:");
for (i=0;i<=s.top-s.base-1;i++)
printf("%d ",s.base[i]);
printf("\n");
return ok;
}
status gettop(sqstack s)//读取
{
selemtype e;
if(s.top==s.base) return error;
e=*(s.top-1);
return e;
}
status destroystack(sqstack &s)//撤销栈
{
free(s.base);
s.top=NULL;
s.stacksize=0;
return ok;
}
status push(sqstack &s,selemtype e)//插入
{
if(s.top-s.base>=s.stacksize){
s.base=(selemtype*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(selemtype));
if(!s.base) exit(overflow);
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e;
}
status pop(sqstack &s,selemtype &e)//删除
{
if(s.top==s.base) return error;
e=*--s.top;
return ok;
}
status in(char c,selemtype op){//in(c,op) //判断c是否是一个运算操作符
switch(c){
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return true;
break;
default:
return false;
break;
}
}
char precede(char op1,char op2){
//判断op1和op2优先级的高低,返回'>','<','='
switch(op1){
case '+':
switch(op2){
case '*':
case '/':
case '(':
return '<';
break;
default:
return '>';
break;
}
break;
case '-':
switch(op2){
case '*':
case '/':
case '(':
return '<';
break;
default:
return '>';
break;
}
break;
case '*':
switch(op2){
case '(':
return '<';
break;
default:
return '>';
break;
}
break;
case '/':
switch(op2){
case '(':
return '<';
break;
default:
return '>';
break;
}
break;
case '(':
switch(op2){
case ')':
return '=';
break;
default:
return '<';
break;
}
break;
case ')':
switch(op2){
default:
return '>';
break;
}
break;
case '#':
switch(op2){
case '#':
return '=';
break;
default:
return '<';
break;
}
break;
default:
return '<';
break;
}
}
selemtype operate(selemtype a,selemtype theta,selemtype b){
//对操作数a,b进行theta运算,并返回运算结果
//theta只能是四则运算符号
int rs_i;
switch(theta){
case '+':
rs_i=a+b;
break;
case '-':
rs_i=a-b;
break;
case '*':
rs_i=a*b;
break;
case '/':
if(b==0){
printf("errror:除数为0.");
exit(0);
}
rs_i=a/b;
break;
default:
printf("Is not a operator.\n");
break;
}
printf("%d %c %d = %d\n",a,theta,b,rs_i);
return rs_i;
}
int main()
{
sqstack optr,opnd;
selemtype c,e,op,x,theta,b,a;
initstack(opnd);//存放运算数
initstack(optr);
push(optr,'#');
initstack(opnd);
c=getchar(); //cout<<"inter"<<c<<endl;
c=c-'0';
while(c!='#'|| gettop(optr)!='#')
{
c=c-'0';//init
if(!in(c,op)) { push(opnd,c); c=getchar(); }//如果不是运算符,进栈 //
else
switch (precede (gettop(optr),c))//栈顶元素优先权判断
{
cout<<"precede"<<precede (gettop(optr),c)<<endl;
case'<':{push(optr,c);c=getchar(); break;}
case'=':{pop(optr,x);c=getchar(); break;}//cout<<"<"<<c<<endl;
case'>':{pop(optr,theta);pop(opnd, b);pop(opnd,a);
//cout<<"b"<<b<<"a"<<a<<"theta"<<theta<<endl;
push(opnd,operate(a,theta,b));
// gettop(opnd,e);
// cout<<e<<endl;
break; }
}
}
cout<<gettop(opnd)<<endl;
destroystack(optr);
destroystack(opnd);
return 0;
}