C语言表达式求值

答案：//表达式求值
//By:jimly
//10/10/2009
//例如：输入2+2（4-6*3）=
//以"="结束,然后回车即出结果
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <assert.h>
typedef float ElemType;
typedef struct Stack
{
 ElemType *base;    // 栈基址
 ElemType *top;    // 栈顶
 int stacksize;    // 栈存储空间的尺寸
} SqStack;
/*------------------------------------------------------------
// 栈的基本操作
------------------------------------------------------------*/
bool InitStack(SqStack *S);
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int  StackLength(SqStack S);
ElemType GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);
/*------------------------------------------------------------
// 表达式求值的操作函数定义
------------------------------------------------------------*/
char Precede(char A1,char A2);
ElemType Operate(ElemType a,ElemType theta,ElemType b);
bool In(char c,char op[]);
ElemType EvaluateExpression();
void Menu();
//////////////////////////////////////////////
// Eval_exdivssion.cpp 表达式求值实现函数 //
//////////////////////////////////////////////
/*------------------------------------------------------------
操作目的： 判定运算符栈的栈顶运算符A1和读入的运算符A2之间优先关系的函数
初始条件： 无
操作结果： 判断出优先关系
函数参数：
  char A1 运算符
  char A2 运算符
返回值：
  char 大小关系
------------------------------------------------------------*/
char Precede(char A1,char A2)
{
 if (A1 == '+' || A1 == '-')
 {
  if (A2 == '+' || A2 == '-' || A2 == ')' || A2 == '=')
  {
   return '>';
  }
  else
   return '<';
 } 
 if (A1 == '*' || A1 == '/')
 {
  if (A2 == '(')
  {
   return '<';
  }
  else
   return '>';
 }
 if (A1 == '(')
 {
  if (A2 == ')')
  {
   return '=';
  }
  if (A2 == '=')
  {
   return 'E';
  }
  else
   return '<';
 }
 if (A1 == ')')
 {
  if (A2 == '(')
  {
   return 'E';
  }
  if (A2 == '=')
  {
   return 'E';
  }
  else
   return '>';
 }
 if (A1 == '=')
 {
  if (A2 == '=')
  {
   return '=';
  }
  else
   return '<';
 }
 else
  return '=';
}
/*------------------------------------------------------------
操作目的： 二元运算a与b的函数
初始条件： 无
操作结果： 返回运算结果
函数参数：
  ElemType a  操作数 
  ElemType theta 操作符
  ElemType b  操作数
返回值：
  ElemType    运算结果
------------------------------------------------------------*/
ElemType Operate(ElemType a,ElemType theta,ElemType b)
{
 switch(char(theta))
 {
 case '+':
  return a += b;
  break;
 case '-':
  return a -= b;
  break;
 case '*':
  return a *= b;
  break;
 case '/':
  if(b==0)
  { 
   printf("除数不能为0！！\n");
   exit(0);
  }
  return a /= b;
  break;
 }
 return 0;
}
/*------------------------------------------------------------
操作目的： 判断字符c是否属于运算符集合op
初始条件： 无
操作结果： 返回判断结果
函数参数：
  char c  要判断的字符
  char op[] 运算符集合
返回值：
  bool  属于返回true 否则返回false   
------------------------------------------------------------*/
bool In(char c,char op[])
{
 for (int i = 0;i<7;i++)
 {
  if (op[i] == c)
   return true;
 }
 return false;
} 
/*------------------------------------------------------------
操作目的： 算术表达式求值的运算符优先算法
初始条件： 无
操作结果： 返回表达式的值
函数参数：
   无
返回值：
   ElemType      运算结果
------------------------------------------------------------*/
ElemType EvaluateExpression()
{
 SqStack OPTR;  //运算符栈
 SqStack OPND;  //运算数栈
 char Ct = '=';  //判断是否结束的标识
 int i = 0,j = 1;
 ElemType e = 0,t = 0,c;
 char op[7] = {'+','-','*','/','(',')','='};
 InitStack(&OPTR);   //初始化
 Push(&OPTR,Ct); 
 InitStack(&OPND); //初始化
  c = (float)getchar();
 while (c!='=' || GetTop(OPTR,&e)!='=')
 {
  if (!In((char)c,op))  //不是运算e符进栈
  {
   while(!In((char)c,op)) //可以是几位数
   {
    t = t*10+(c-48);
    c = (float)getchar();
   }
   Push(&OPND,t);
   t = 0;
  }
  else
  {
   switch (Precede((char)GetTop(OPTR,&e),(char)c))
   {
   case '<'://栈顶元素优先权低
    Push(&OPTR,c);
    c = (float)getchar();
    break;
   case '='://脱括号并接受下个字符
    ElemType x;
    Pop(&OPTR,&x);
    c = (float)getchar();
    break;
   case '>'://退栈并将运算结果入栈
    ElemType b,theta,a;
    Pop(&OPTR,&theta);
    Pop(&OPND,&b);
    Pop(&OPND,&a);
    Push(&OPND,Operate(a,theta,b));
    break;
   case 'E':
    printf("括号不匹配！！\n");
    exit(0);
    break;
    
   }
  }
 }
 ElemType tem = GetTop(OPND,&e);
 DestroyStack(&OPND);
 DestroyStack(&OPTR);
 return tem;
}
/***
*DynaSeqStack.cpp - 动态顺序栈，即栈的动态顺序存储实现
****/
const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT  = 10;  // 分配内存的增量
/*------------------------------------------------------------
操作目的： 初始化栈
初始条件： 无
操作结果： 构造一个空的栈
函数参数：
  SqStack *S 待初始化的栈
返回值：
  bool  操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
 assert(S != NULL);
 S->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
 
 if(S->base == NULL) return false;
 S->top = S->base;
 S->stacksize = STACK_INIT_SIZE;
 return true;
}
/*------------------------------------------------------------
操作目的： 销毁栈
初始条件： 栈S已存在
操作结果： 销毁栈S
函数参数：
  SqStack *S 待销毁的栈
返回值：
  无
------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
 assert(S != NULL);
 free(S->base);
 S->top = S->base = NULL;
}
/*------------------------------------------------------------
操作目的： 判断栈是否为空
初始条件： 栈S已存在
操作结果： 若S为空栈，则返回true，否则返回false
函数参数：
  SqStack S 待判断的栈
返回值：
  bool  是否为空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
 assert((S.base != NULL) && (S.top != NULL));
 return(S.base == S.top);
}
/*------------------------------------------------------------
操作目的： 得到栈的长度
初始条件： 栈S已存在
操作结果： 返回S中数据元素的个数
函数参数：
  SqStack S 栈S
返回值：
  int   数据元素的个数
------------------------------------------------------------*/
int StackLength(SqStack S)
{
 assert((S.base != NULL) && (S.top != NULL));
 return(S.top-S.base);
}
/*------------------------------------------------------------
操作目的： 得到栈顶元素
初始条件： 栈S已存在
操作结果： 用e返回栈顶元素
函数参数：
  SqStack S 栈S
  ElemType *e 栈顶元素的值
返回值：
  bool  操作是否成功
------------------------------------------------------------*/
ElemType GetTop(SqStack S, ElemType *e)
{
 assert((S.base != NULL) && (S.top != NULL));
 if(StackEmpty(S)) return false;
 *e = *(S.top-1);
 return *e;
}
/*------------------------------------------------------------
操作目的：

上一个：模拟人工发牌程序 C语言
下一个：c语言程序设计 单词统计