数据结构题目算术表达式求值一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含+、-、*、/等四种运算符，界限符有左右圆括号和

Question

数据结构题目
算术表达式求值
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含+、-、*、/等四种运算符，界限符有左右圆括号和表达式结束符“#”，如：(7+15)*(23-28/4)#。编程按照算术运算规则，求算术表达式的值。
提示：通过“栈”实现。
请给出源代码

Answer 1

本人原创，已通过编译，速度采纳亲
#include
#include
#define MAXSIZE 100
#define INCREMENT 10
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char elemtype;
typedef struct
{
elemtype * top;
elemtype * base;
int stacksize;
}stack;
int initstack(stack &S)
{
S.base=(elemtype *)malloc(MAXSIZE * sizeof(elemtype));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}
elemtype gettop(stack S)
{
if(S.top==S.base) return '\0';
return *(S.top-1);
}
int push(stack &S,elemtype e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(elemtype *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(elemtype));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=INCREMENT;
}
*S.top++=e;
return OK;
}
int pop(stack &S,elemtype &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
int in(elemtype c)
{
if('0'<=c&&'9'>=c)
return 0;
return 1;
}
int exchange(elemtype c)
{
switch(c)
{
case '+':return 1;
case '-':return 2;
case '*':return 3;
case '/':return 4;
case '(':return 5;
case ')':return 6;
case '#':return 7;
}
}
int precede(char a,char b)
{
int x,y;
x=exchange(a)-1;
y=exchange(b)-1;
int list[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,-2},{1,1,1,1,-2,1,1},{-1,-1,-1,-1,-1,-2,0}};
return list[x][y];
}
elemtype operate(elemtype a,elemtype theta,elemtype b)
{
switch(theta)
{
case '+':
return (a-'0'+b);
case '-':
return (a-b+'0');
case '*':
return ((a-'0')*(b-'0')+'0');
case '/':
return ((a-'0')/(b-'0')+'0');
}
}

elemtype count()
{
stack optr,opnd;
initstack(optr);
push(optr,'#');
initstack(opnd);
elemtype c;
c=getchar();
elemtype x,a,b,theta;
while(c!='#'||gettop(optr)!='#')
{
if(!in(c))
{
push(opnd,c);
c=getchar();
}
else
switch(precede(gettop(optr),c))
{
case -1:
push(optr,c);
c=getchar();
break;
case 0:
pop(optr,x);
c=getchar();
break;
case 1:
pop(optr,theta);
pop(opnd,b);
pop(opnd,a);
push(opnd,operate(a,theta,b));
break;
}
}
return gettop(opnd);
}
int main(void)
{
printf("输入表达式\n");
int m=count()-'0';
printf("结果为%d\n",m);
return 0;
}