ch3_express.c

本人讲授数据结构课程时的所写的示例程序

/*
栈的应用：表达式计算
author: kk.h
date: 2006.9
http://www.cocoon.org.cn
*/

#include "stdio.h"
#define StackSize 100
typedef int ElemType;
typedef struct {
  ElemType elem[StackSize];
  int top;
}SqStack;

InitStack(SqStack *pS)
{
  pS->top=0; /* top指向栈顶的上一个元素 */
}

int Push(SqStack *pS,ElemType e)
{
  if (pS->top==StackSize-1)   /* 栈满 */
    return 0;

  pS->elem[pS->top]=e;
  pS->top=pS->top+1;
  return 1;
}

int Pop(SqStack *pS,ElemType* pe)
{
  if (pS->top==0)  /* 栈空 */
    return 0;

  pS->top = pS->top - 1;
  *pe = pS->elem[pS->top];
  return 1;
}

ElemType GetTop(SqStack *pS)
{
  return pS->elem[pS->top-1];
}

int IsOptr(char c)
{
  if (c=='+'|| c=='-'||c=='*'||c=='/'||c=='('||c==')')
    return 1;
  else
    return 0;
}

int Order(int c1,int c2)
{
  int or[][6]={{1,1,-1,-1,-1,1},{1,1,-1,-1,-1,1},{1,1,1,1,-1,1},{1,1,1,1,-1,1},{-1,-1,-1,-1,-1,2},{1,1,1,1,-2,1}};
  return or[c1][c2];
}

int Operate(ElemType a,ElemType theta,ElemType b)
{
  switch (theta){
    case 0: return a+b;
    case 1: return a-b;
    case 2: return a*b;
    case 3: return a/b;
  }
}

int optr2num(char c)
{
  switch (c){
    case '+': return 0;
    case '-': return 1;
    case '*': return 2;
    case '/': return 3;
    case '(': return 4;
    case ')': return 5;
  }  
}

main()
{
  SqStack Soptr,Snum;
  ElemType a,b,theta;
  char exp[]="2*(3*(3-5)+2*4)";
  int i,len;

  InitStack(&Soptr);
  InitStack(&Snum);

  len=strlen(exp);

  i=0;
  while(i<len || Soptr.top>0) {
  
    /* 当字符没读取完毕，而且该字符是操作数则直接入栈 */
    if (i<len && !IsOptr(exp[i])) {
      Push(&Snum,exp[i]-'0');
      printf("\na_%d",exp[i]-'0');
      i=i+1;
      continue;
    }


    /* 当栈空或者操作符>栈顶元素，操作符入栈 */
    if (Soptr.top==0 || Order(GetTop(&Soptr),optr2num(exp[i]))<0) {
      Push(&Soptr,optr2num(exp[i]));
      printf("\nb_%c",exp[i]);
      i=i+1;
      continue;
    }

    /* 右括号遇到左括号 */
    if (Order(GetTop(&Soptr),optr2num(exp[i]))==2) {
      Pop(&Soptr,&theta);
      i=i+1;
      printf("\nc_)");
      continue;
    }

    /* 当字符读取完毕或者操作符<栈顶元素，退栈、计算，结果压入NUM栈 */
    if (i==len || Order(GetTop(&Soptr),optr2num(exp[i]))>0) {
      Pop(&Soptr,&theta);
      Pop(&Snum,&b); Pop(&Snum,&a);
      Push(&Snum,Operate(a,theta,b));
      printf("\nd_%d",Operate(a,theta,b));
      continue;
    }
  }

  Pop(&Snum,&a);
  printf("\nresult=%d",a);

  getch();
}