表达式运算(栈)

2019PHP高薪工程师学习路线图....>>>

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW 0
typedef int SElemType; 
char m[20];
typedef enum aa{FALSE,TRUE} Status;
 
typedef struct{
 SElemType *base;
 SElemType *top;
 int stacksize;
}SqStack;
 
int N;
unsigned n;
 
Status InitStack(SqStack &S)
{
 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if(!S.base)
  return FALSE;
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
 return TRUE;
}
 
Status Pop(SqStack &S, SElemType &e)
{
 if(S.top==S.base)
  return FALSE;
 e = *--S.top;
 return TRUE;
}
 
Status Push(SqStack &S, SElemType e)
{
 if(S.top-S.base >= S.stacksize)
 {
  S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
  if(!S.base)
   return FALSE;
  S.top = S.base + S.stacksize;
  S.stacksize += STACKINCREMENT;
 }
 *S.top++ = e;
 return TRUE;
}
 
Status GetTop(SqStack S, SElemType &e)
{
 if(S.top > S.base)
 {
  e = *(S.top-1);
  return TRUE;
 }
 else
  return FALSE;
}
 
Status StackEmpty(SqStack S)
{
 if(S.top == S.base)
  return TRUE;
 else
  return FALSE;
}
 
Status In(SElemType c) //判断c是否为运算符
{
 switch(c)
 {
  case'+':
  case'-':
  case'*':
  case'/':
  case'(':
  case')':
  case'#':
   return TRUE;
  default:
   return FALSE;
 }
}
 
char Precede(SElemType  t1, SElemType  t2) //判断两符号的优先关系
{
 SElemType f;
 switch(t2)
 {
  case'+':
  case'-':
   if(t1=='('||t1=='#')
   f='<';
  else
   f='>';
   break;
  case'*':
  case'/':
   if(t1=='*'||t1=='/'||t1==')')
   f='>';
  else
   f='<';
   break;
  case'(':
   if(t1==')')
   {   
    printf("括号不匹配\n");
    exit(OVERFLOW);
   }
  else
   f='<';
   break;
  case')':
   switch(t1)
   {
    case'(':
     f='=';
     break;
    case'#':
     printf("缺乏左括号\n");
     exit(OVERFLOW);
     default:
     f='>';
   }
  break;
  case'#':
   switch(t1)
   {
    case'#':
     f='=';
     break;
    case'(':
     printf("缺乏右括号\n");
     exit(OVERFLOW);
     default:
     f='>';
   }
 }
 return f;
}
 
SElemType Operate(SElemType a,SElemType theta,SElemType b) //做四则运算a theta b,返回运算结果
{
 SElemType c;
  switch(theta)
  {
   case'+':
    return a+b;
   case'-':
    return a-b;
   case'*':
    return a*b;
  }
 return a/b;
}
 
SElemType EvaluateExpression()
{
 SqStack OPTR, OPND;
 SElemType a, b, c, x;
 int i=0;
 InitStack(OPTR);
 InitStack(OPND);
 Push(OPTR, '#');
 c=m[i++];
 GetTop(OPTR, x);
 while(c != '#' || x!='#')
 {
  if(In(c))
   switch(Precede(x, c))
   {
    case '<':
     Push(OPTR, c);
     c=m[i++];
     break;
    case '=':
     Pop(OPTR, x);
     c=m[i++];
     break;
    case '>':
     Pop(OPTR, x);
     Pop(OPND, b);
     Pop(OPND, a);
     Push(OPND, Operate(a, x, b));
     break;
   }
  else if(c>='0' && c<='9')
  {
   Push(OPND, c-48);
   c=m[i++];
  }
  else
  {
   printf("出现非法字符\n");
   exit(OVERFLOW);
  }
  GetTop(OPTR, x);
 }
 Pop(OPND, x);
 if(!StackEmpty(OPND))
 {
  printf("表达式不正确\n");
  exit(OVERFLOW);
 }
 return x;
}
 
void main()
{
   int x;
   
   while(1)
   {
 printf("1.输入表达式\n2.输出表达式\n3.判断表达式的括号是否匹配并计算表达式的值\n4.退出\n");
    printf("请选择1-4\n");
  scanf("%d",&x);
   if(x==1)
   {
 printf("请输入算式表达式(输入的值要为0-9),中间运算值和输出结果为-128~127\n");
        scanf("%s", m);
   }
    else if(x==2)
 { 
  printf("输出表达式\n");
  printf("%s\n", m);
 }
        else if(x==3)
  {
  printf("判断表达式的括号是否匹配并计算表达式的值\n");
     printf("%d\n",EvaluateExpression());
  }
  
             else if(x==4) 
    { 
     break;
    }
         else 
      { 
         printf("输入的为非法字符");
            break;
      }
}
}