第二题.cpp

几个常用的数据结构算法：堆栈、链表、二叉树、图等。

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

#define OPSETSIZE 7
#define N 10
unsigned char Prior[7][7] = {     // 表3.1  算符间的优先关系
  	  '>',  '>',    '<',    '<',    '<',    '>',    '>',
	  '>',  '>',    '<',    '<',    '<',    '>',    '>',
	  '>',	'>',	'>',	'>',	'<',	'>',	'>',
	  '>',	'>',	'>',	'>',	'<',	'>',	'>',	
	  '<',	'<',	'<',	'<',	'<',	'=',	' ',
	  '>',	'>',	'>',	'>',	' ',	'>',	'>',
	  '<',	'<',	'<',	'<',	'<',	' ',	'='
};	
char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};
typedef struct  {
	char *base;
	char *top;
    int stacksize;
} StackChar;
typedef struct {
	float *base;
	float *top;
    int stacksize;
} StackFloat;
	
float Operate(float a, unsigned char theta, float b);
int In(char Test,char* TestOp);
char precede(char Aop, char Bop);
int Popc(StackChar *sq,char e);
int Pushc(StackChar *sq,char e);
int InitStackc(StackChar *sq);
float Popf(StackFloat *sq,float e);
int Pushf(StackFloat *sq,float e);
int InitStackf(StackFloat *sq);
float EvaluateExpression(char* MyExpression);
char GetTopc(StackChar *sq);
float GetTopf(StackFloat *sq);


typedef char ElemType;     
typedef ElemType OperandType;   //操作数
typedef char OperatorType;


void main()
{
	float a;int i;
	char b[50];
	printf("请输入正确地表达式以'#'结尾:\n");
	for(i=0;b[i-1]!='#'&&i<50;i++)
	{
		scanf("%c",&b[i]);
	}
	a=EvaluateExpression( b);
	printf("%f\n",a);
}

		
float EvaluateExpression(char* MyExpression) {  // 算法3.4
   // 算术表达式求值的算符优先算法。
   // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。
   StackChar OPTR;    // 运算符栈，字符元素
   StackFloat OPND;    // 运算数栈，实数元素
   char TempData[20];
   float Data,a,b;
   char theta,*c,x,Dr[2];
  
   
   InitStackc (&OPTR);
   Pushc (&OPTR, '#');
   InitStackf (&OPND);
   c = MyExpression;
   strcpy(TempData,"\0");
   while (*c!= '#' || GetTopc(&OPTR)!= '#') {
      if (!In(*c, OPSET)) {
      	 Dr[0]=*c;
      	 Dr[1]='\0';
         strcat(TempData,Dr);
         c++;
         if(In(*c,OPSET)) {
            Data=(float)atof(TempData);
            Pushf(&OPND, Data);
            strcpy(TempData,"\0");
         } 
      } else {   // 不是运算符则进栈
         switch (precede(GetTopc(&OPTR), *c)) { 
            case '<':   // 栈顶元素优先权低
                 Pushc(&OPTR, *c);  
                 c++;
                 break;
            case '=':   // 脱括号并接收下一字符
                 Popc(&OPTR, x);   
                 c++;
                 break;
            case '>':   // 退栈并将运算结果入栈
                 theta=Popc(&OPTR, theta);
                 b=Popf(&OPND, b);  
                 a=Popf(&OPND, a);                      
                 Pushf(&OPND, Operate(a, theta, b)); 
                 break;
         } // switch
      }
   } // while
   return GetTopf(&OPND);
} // EvaluateExpression

float Operate(float a,unsigned char theta, float b) {
   switch(theta) {
      case '+': return a+b;
      case '-': return a-b;
      case '*': return a*b;
      case '/': return a/b;
      default : return 0;
   } 
}	

int In(char Test,char* TestOp) {
   bool Find=false;
   for (int i=0; i< OPSETSIZE; i++) {
      if (Test == TestOp[i]) Find= true;
   }
   return Find;
}


int ReturnOpOrd(char op,char* TestOp) {
   int i;
   for(i=0; i< OPSETSIZE; i++) {
      if (op == TestOp[i]) return i;
   }
   return 0;
}

char precede(char Aop, char Bop) {
   return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
}
int InitStackc(StackChar *sq)
{

	sq->base=(char *)malloc(N*sizeof(char));
	if(!sq->base)return false;
	sq->top=sq->base;
	sq->stacksize=N;
	return true;
}
int Pushc( StackChar *sq,char e)
{
	if(sq->top-sq->base>=sq->stacksize)
	{
		sq->base=(char *)realloc(sq->base,(sq->stacksize+N)*sizeof(char));
    	if(!sq->base)return false;
     	sq->top=sq->base+sq->stacksize;
    	sq->stacksize+=N;
	}
	*sq->top++=e;
	return true;
}
int Popc(StackChar *sq,char e)
{
	if(sq->top==sq->base)return false;
	e=*--sq->top;
	return e;
}
int InitStackf(StackFloat *sq)
{
	sq->base=(float *)malloc(N*sizeof(float));
	if(!sq->base)return false;
	sq->top=sq->base;
	sq->stacksize=N;
	return true;
}
int Pushf(StackFloat *sq,float e)
{
	if(sq->top-sq->base>=sq->stacksize)
	{
		sq->base=(float *)realloc(sq->base,(sq->stacksize+N)*sizeof(float));
    	if(!sq->base)return false;
     	sq->top=sq->base+sq->stacksize;
    	sq->stacksize+=N;
	}
	*sq->top++=e;
	return true;
}
float Popf(StackFloat *sq,float e)
{
	if(sq->top==sq->base)return false;
	e=*--sq->top;
	return e;
}
char GetTopc(StackChar *sq)
{
	if(sq->top==sq->base) return '#';
	return(*(sq->top-1));
	 
}
float GetTopf(StackFloat *sq)
{
	if(sq->top==sq->base) return false;
	return(*(sq->top-1));
	
}