实验2的对中缀表达式求值.c

演示用算符优先法对中序算术表达式求值的过程。 程序执行的命令包括： （1）构造两个空栈

#include<stdio.h>
#include<stdlib.h>
#define  stackinitsize 100     //存储空间初始分配量
#define  stackincrement 10     //存储空间分配增量
#define  OVERFLOW  -1
typedef struct
{
	char *base;          //在栈构造之前和销毁之后，base的值为NULL
	char *top;           //栈顶指针
	int stacksize;      //当前已分配的存储空间，以元素为单位
}sqstack;        //定义栈的类型

void initstack(sqstack *s)    //创建一个空栈s
{
	s->base=(char*)malloc(stackinitsize*sizeof(char));
	if(!s->base)  exit(OVERFLOW);      //存储分配失败
	s->top=s->base;
	s->stacksize=stackinitsize;

}//initstack

char gettop(sqstack *s)        //得到栈顶元素并返回其值
{
	if(s->top==s->base)return 0;
	return *(s->top-1);
}//gettop

void push(sqstack *s,char e)   //插入元素为e的栈顶元素
{
	if(s->top-s->base>=s->stacksize)     //栈满，追加存储空间
	{
	    s->base=(char*)realloc(s->base,(s->stacksize +stackincrement)*sizeof(char));	
		if(!s->base)  exit(OVERFLOW);      //存储分配失败
		s->top =s->base +s->stacksize ;
		s->stacksize +=stackincrement;
	
	}
	*s->top++=e;

}//push

int pop(sqstack *s,char *e)//如果栈不空，则将栈顶元素出栈，并用1返回
{
	if(s->top==s->base)return 0;
	*e=*--s->top;
	return 1;
}//pop

char precede(char a1,char a2)//对两个符号a1,a2的优先级进行比较
{
	 if((a1=='+'&&a2=='+')||(a1=='+'&&a2=='-')||(a1=='+'&&a2=='#')||(a1=='+'&&a2==')')||(a1=='-'&&a2=='+')||(a1=='-'&&a2=='-')||(a1=='-'&&a2==')')||
		(a1=='-'&&a2=='#')||(a1=='*'&&a2=='+')||(a1=='*'&&a2=='-')||(a1=='*'&&a2=='*')||(a1=='*'&&a2=='/')||(a1=='*'&&a2==')')||(a1=='*'&&a2=='#')||
		(a1=='/'&&a2=='+')||(a1=='/'&&a2=='-')||(a1=='/'&&a2=='*')||(a1=='/'&&a2=='/')||(a1=='/'&&a2==')')||(a1=='/'&&a2=='#')||(a1==')'&&a2=='+')||(a1==')'&&a2=='-')
		||(a1==')'&&a2=='*')||(a1==')'&&a2=='/')||(a1==')'&&a2==')')||(a1==')'&&a2=='#'))
	return '>';           
	else if((a1=='('&&a2==')')||(a1=='#'&&a2=='#'))
	     	return '=';    

	else   return '<';   
}//precede

int operate(int a,char s,int b)//进行a运算符b的运算，并返回结果
{
	int r;
	if(s=='+')r=(a-48)+(b-48);   
	if(s=='-')r=(a-48)-(b-48);   
	if(s=='*')r=(a-48)*(b-48);   
	if(s=='/')r=(a-48)/(b-48);   
	return (r+48);  //返回的是r的ASCII代码值
}//operate

void main()
{
	char a,b, c,x, theta;
	sqstack optr;
	sqstack opnd;
	printf("请输入一个中缀表达式，并以‘＃’结束：\n");  
	initstack(&optr);
	push(&optr,'#');
	initstack(&opnd);
	c=getchar(); 
   
	while(c!='#'||gettop(&optr)!='#')  //若字符c不是结束符'#'则进行以下操作
	{
		if(c>=48&&c<=57)//判断字符c是否为数，若是数则进入数栈 
		{
			push(&opnd,c);
			c=getchar();
		}
		else 
		{
			switch(precede(gettop(&optr),c))
			{
				case '<':    //栈顶元素优先权低               
					{push(&optr,c);
					c=getchar();
					break;}
				case '=':   //脱括号并接收下一个字符             
					{	pop(&optr,&x);
					c=getchar();
					break;}
				case '>':    //退栈并将运算结果入栈              
					{	
					pop(&optr,&theta);
					pop(&opnd,&b);
					pop(&opnd,&a);
					push(&opnd,operate(a,theta,b));
					break;}
				}//switch
		}//while
	}
	printf("输出结果为：\n"); 
	printf("%d\n\n",(gettop(&opnd)-48));//最终结果是ASCII代码形式，要将其转化过来
}//main