biaodashiqiuzhi.cpp

对于一个表达式求值 用堆栈实现 数据结构第一个实验 没有做附加功能

#include<stdio.h>
#include<stdlib.h>
#define INITSIZE 100
typedef char ElemType;
typedef struct
{
int top;
ElemType   *base;
int        stacksize;
}sqstack;
#define INITSIZE 100
typedef char ElemType;
typedef struct
{
int top;
ElemType   *base;
int        stacksize;
}sqstack;
void main()
{
sqstack OPTR,OPND;    //OPTR、OPND分别表示运算符栈与运算数栈
ElemType a,b,c,x;
initstack(&OPTR);
initstack(&OPND);
push(&OPTR,'\n');
printf("请输入算术表达式（输入的值在0~9之间）:");
c=getchar();
gettop(&OPTR,&x);
while(c!='\n'||x!='\n')
{
if(in(c))
switch(precede(x,c))
{
case '<':  push(&OPTR,c);
c=getchar();
break;
case '=':  pop(&OPTR,&x);
c=getchar();
break;
case '>':  pop(&OPTR,&x);
pop(&OPND,&b);
push(&OPND,operate(a,x,b));
break;
 }
else if(c>='0'&&c<='9')
{
	push(&OPND,c-48);
c=getchar();
}
else
 {
	printf("出现非法字符！！！");
exit(0);
}
gettop(&OPTR,&x);
 }
pop(&OPND,&a);
if(!stackempty(&OPND))
{
printf("表达式不正确！！！");
exit(0);
}
printf("%d\n",a);
}
void initstack(sqstack *s)           //创建空栈
{
s->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));
s->top=0;
s->stacksize=INITSIZE;
}
int push(sqstack *s,ElemType x)       //把元素入栈
{
s->base[s->top++]=x;
return 1;
}
int pop(sqstack *s,ElemType *e)      //元素出栈
{
if(s->top==0)  return 0;
else
*e=s->base[--s->top];
return *e;
}
int stackempty(sqstack *s)            //判断栈空
{
if(s->top==0)     return 1;
else             return 0;
}
int gettop(sqstack *s,ElemType *e)    //e返回是s的栈顶元素
{
if(s->top>0)
{
*e=s->base[s->top-1];
return 1;
}
else
return 0;
}
int in(char c)                            // 判断c是否为7种运算符之一
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '\n':  return 1;
default  :  return 0;
}
}
char precede(char t1,char t2)             //    判断两字符的优先关系
{
char f;
switch(t2)
{
case '+':
case '-':  if(t1=='('||t1=='\n')
f='<';   //t1<t2
else
f='>';   //t1>t2
break;
case '*':
case '/':  if(t1=='*'||t1=='/')
f='>';    //t1>t2
else
f='<';   //t1<t2
break;
case '(':  if(t1==')')
		   {
printf("括号内无数值！！！");
exit(0);
		   }
else
f='<';     //t1<t2
break;
case ')':  switch(t1)
		   {
case '(': f='=';   //t1=t2
break;
case '\n': printf("括号不匹配！！！");
exit(0);
default  : f='>';  //t1>t2
		   }
break;
case '\n': switch (t1)
		   {
case '\n': f='=';  //t1=t2
break;
case '(':  printf("括号不匹配！！！");
exit(0);
default :  f='>';  //t1>t2
		   }
		   }
return f;
}
char operate(char a,char theta,char b)     //表达式求值
{
switch(theta)
{
case '+' :return a+b;
case '-' :return a-b;
case '*' :return a*b;
default  :return a/b;
}
}