表达式求值.doc

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define STACK_INIT_SIZE 100  //初始分配量
#define STACKINCREMENT 10    //存储空间的分配增量

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

typedef struct
{
 ElemType *base;
 ElemType *top;
 int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
 //构造一个空栈S
    S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!S.base) exit (OVERFLOW);
 S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status GetTop(SqStack S){
 ElemType e;
 if (S.top == S.base) return ERROR;
 e = *(S.top-1);
 return e;
}

Status Push (SqStack &S,ElemType e)
{
 //插入元素e为新的栈顶元素
 if (S.top - S.base >= S.stacksize){
  S.base = (ElemType *) realloc ( S.base,
   (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
  if(!S.base) exit (OVERFLOW);
  S.top = S.base + S.stacksize;
  S.stacksize += STACKINCREMENT;
 }
 *S.top++ = e;
 return OK;
}

Status Pop (SqStack &S,ElemType &e){
 //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    if(S.top == S.base) return ERROR;
    e = * --S.top;
    return OK;
}

char In(char c,char OP[])
{
 if(c>=35 && c<=47)
  return 1;
 else return 0;
}

char OP[8]={'+','-','*','/','(',')','#','\0'};
int m[7][7]={1,1,2,2,2,1,1,

       1,1,2,2,2,1,1,

    1,1,1,1,2,1,1,
    1,1,1,1,2,1,1,
    2,2,2,2,2,0,-1,
    1,1,1,1,-1,1,1,
    2,2,2,2,2,-1,0};//1 >  2 <  0 =  -1 不存在

char Precede(char i,char j)
{
 int a,b; char *p;
 for(p=OP,a=0;*p!='\0';p++,a++)
  if(*p==i) break;
 for(p=OP,b=0;*p!='\0';p++,b++)
  if(*p==j) break;
  if(m[a][b]==1) return '>';
  else if(m[a][b]==2) return '<';
  else if(m[a][b]==0) return '=';
  else return 'O';
}

char Operate(char a,char theta,char b)
{
 if(a>47) a=atoi(&a);
 if(b>47) b=atoi(&b);
 switch(theta)
 { 
 case '+': return a+b;
    break;
 case '-': return a-b;
   break;
 case '*': return a*b;
   break;
 case '/': return a/b;
   break;
 }
}

OperandType EvaluateExpression()
{
 SqStack OPTR,OPND;
 OperandType a,b,c; OperatorType theta;
 InitStack(OPTR); Push(OPTR,'#');
 InitStack(OPND); c=getchar();
 while (c!='#' || GetTop(OPTR)!='#')
 {
  if (!In(c,OP)){Push(OPND,c);c=getchar();}
  else
   switch(Precede(GetTop(OPTR),c))
  {
   case '<' :
    Push(OPTR,c); c = getchar();
    break;
   case '=' :
    Pop(OPTR,c); c = getchar();
    break;
   case '>' :
    Pop(OPTR,theta);
    Pop(OPND,b); Pop(OPND,a);
    Push(OPND,Operate(a,theta,b));
    break;
  }
 }
 return GetTop(OPND);
}

void main()
{
 printf("(以#为结束符)\n");
 printf("请输入：\n");
 int a;
 a=(int)EvaluateExpression();
 printf("%d",a);
 getch();
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define error 0
#define ok 1
#define overflow -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OPSETSIZE 7
char OPSET[OPSETSIZE]=;
unsigned char Prior[7][7] = { // 算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
};
typedef int Status;

template <typename T>
struct SqStack
{
T *top;
T *base;
int stacksize;

};//顺序栈结构模板

template <typename T1,typename T2>
Status InitStack(T1 &S)
{
S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2));
if(!S.base) exit (overflow);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return ok;
}//初始化栈函数模板

template <typename T1,typename T2>
Status Push(T1 &S,T2 e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2));
if(!S.base) exit (overflow);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return ok;
}//入栈函数模板

template <typename T1,typename T2>
Status Pop(T1 &S,T2 &e)
{
if(S.top==S.base) return error;
e=*--S.top;
return ok;
}//出栈函数模板

template <typename T1,typename T2>
T2 GetTop(T1 S)
{
if(S.top==S.base)
return error;
else
return *(S.top-1);

}//获取栈顶元素模板

Status In(char Test,char* TestOp) {
bool Find=false;
for (int i=0; i< OPSETSIZE; i++) {
if (Test == TestOp[i]) Find= true;
}
return Find;
}//判断是否为运算符

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 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)];
}//ReturnOpOrd和precede组合，判断运算符优先级

float EvaluateExpression() {
// 算术表达式求值的算符优先算法。
// 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
SqStack<char> OPTR; // 运算符栈，字符元素
SqStack<float> OPND; // 运算数栈，实数元素
char TempData[20];
float Data,a,b;
char theta,c,x,Dr[2];

InitStack<SqStack<char>,char> (OPTR);
Push (OPTR, '#');
InitStack <SqStack<float>,float>(OPND);
strcpy(TempData,"\0");//将TempData置为空
c=getchar();
while (c!= '#' || GetTop<SqStack<char>,char>(OPTR)!= '#')
{
if (!In(c, OPSET))
{
Dr[0]=c;
Dr[1]='\0';//存放单个数
strcat(TempData,Dr);//将单个数连到TempData中，形成字符串
c=getchar();
if(In(c,OPSET))//如果遇到运算符，则将字符串TempData转换成实数，入栈，
并重新置空
{
Data=(float)atof(TempData);
Push(OPND, Data);
strcpy(TempData,"\0");
}
}
else
{ // 不是运算符则进栈
switch (precede(GetTop<SqStack<char>,char>(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
return GetTop<SqStack<float>,float>(OPND);
} // EvaluateExpression

void main()
{
printf("请输入表达式（end #）：\n");
printf("%f\n",EvaluateExpression());
}