C++利用链栈实现表达式求值

本文实例为大家分享了C++利用链栈实现表达式求值的具体代码，供大家参考，具体内容如下

#include<iostream.h>
typedef int Status;
typedef char Cstack;
#define OK 1
#define ERROR 0
 
typedef struct StackNode
{
  Cstack data;
  struct StackNode *next;
}StackNode,*LinkStack;
 
Status InitStack(LinkStack &S)
{
  S=NULL;
  return OK;
}
Status Push(LinkStack &S,Cstack e)
{
  StackNode *p;
  p=new StackNode;
  p->data=e;
  p->next=S;
  S=p;
  return OK;
}
Status Pop(LinkStack &S,Cstack &e)
{
  StackNode *p;
  if(S==NULL) return ERROR;
  e=S->data;
  p=S;
  S=S->next;
  delete p;
  return OK;
}
Cstack GetTop(LinkStack S)
{
  if(S!=NULL)
  return S->data;
}
Status In(Cstack ch)
{
  cin>>ch;
  if(ch=='+')
    return OK;
  else if(ch=='-')
    return OK;
  else if(ch=='*')
    return OK;
  else if(ch=='/')
    return OK;
  else if(ch=='#')
    return OK;
  else
    return ERROR;
}
Cstack Precede(Cstack t1,Cstack t2)
{
  switch(t1)
  {
  case '+':
    switch(t2)
    {
    case '+':return '>';break;
    case '-':return '>';break;
    case '*':return '<';break;
    case '/':return '<';break;
    case '(':return '<';break;
    case ')':return '>';break;
    case '#':return '>';break;
    }
    break;
    case '-':
      switch(t2)
    {
    case '+':return '>';break;
    case '-':return '>';break;
    case '*':return '<';break;
    case '/':return '<';break;
    case '(':return '<';break;
    case ')':return '>';break;
    case '#':return '>';break;
    }
    break;
    case '*':
      switch(t2)
    {
    case '+':return '>';break;
    case '-':return '>';break;
    case '*':return '>';break;
    case '/':return '>';break;
    case '(':return '<';break;
    case ')':return '>';break;
    case '#':return '>';break;
    }
    break;
    case '/':
      switch(t2)
    {
    case '+':return '>';break;
    case '-':return '>';break;
    case '*':return '>';break;
    case '/':return '>';break;
    case '(':return '<';break;
    case ')':return '>';break;
    case '#':return '>';break;
    }
    break;
    case '(':
      switch(t2)
    {
    case '+':return '<';break;
    case '-':return '<';break;
    case '*':return '<';break;
    case '/':return '<';break;
    case '(':return '<';break;
    case ')':return '=';break;
    case '#':return '>';break;
    }
    break;
    case ')':
      switch(t2)
    {
    case '+':return '>';break;
    case '-':return '>';break;
    case '*':return '>';break;
    case '/':return '>';break;
    case '(':return '=';break;
    case ')':return '>';break;
    case '#':return '>';break;
    }
    break;
    case '#':
      return '=';
    break;
  }
}
Cstack Operator(Cstack t1,Cstack t2,Cstack t3)
{
  t1=t1-48;
  t3=t3=48;
  int c;
  switch(t2)
  {
  case '+':
    c=t1+t2+48;
    return c;
    break;
  case '-':
    c=t1-t2+48;
    return c;
    break;
  case '*':
    c=t1*t2+48;
    return c;
    break;
  case '/':
    c=t1/t2+48;
    return c;
    break;
  }
}  
void main()
{
  LinkStack OPTR,OPAN;
  Cstack cha1,cha2,x,cha,thea;
  InitStack(OPTR);
  InitStack(OPAN);
  Push(OPTR,'#');
  cout<<"输入表达式的中间值及最终结果局限于0～9之间的个位数并以#号结束"<<endl;
  while(cha!='#'||GetTop(OPTR)!='#')
  {
    cin>>cha;
    if(!In(cha))
      Push(OPAN,cha);
    else
      switch(Precede(GetTop(OPTR),cha))
      {
      case '<':
        Push(OPTR,cha);
        cin>>cha;
          break;
      case '>':
        Pop(OPTR,thea);
        Pop(OPAN,cha1);
        Pop(OPAN,cha2);
        Push(OPAN,(cha1,thea,cha2));
          break;
      case '=':
        Pop(OPTR,x);
        break;
      }
  }
  cout<<GetTop(OPAN)<<endl;
  return;
}

以上就是本文的全部内容，希望对大家学习C++程序设计有所帮助。