rpn.cpp

用户输入一个字符串

#include<string>
#include<iostream>
#include<csetjmp>
using namespace std;

static string expr;
static int pos;
static jmp_buf errjb;

struct BiTree
{
 string data;
 BiTree* lchild;
 BiTree* rchild;
};

BiTree* T_MulDiv();
BiTree* F_ExpNum();

//E->TE+|TE-|T
BiTree* E_AddSub()
{
 if(expr[pos]=='+'||expr[pos]=='-')
 {
  BiTree* ret=new BiTree;
  ret->data=expr[pos--];
  ret->rchild=E_AddSub();
  ret->lchild=T_MulDiv();
  return ret;
 }
 return T_MulDiv();
}

//T->FT*|FT/|F
BiTree* T_MulDiv()
{
 if(expr[pos]=='*'||expr[pos]=='/')
 {
  BiTree* ret=new BiTree;
  ret->data=expr[pos--];
  ret->rchild=T_MulDiv();
  ret->lchild=F_ExpNum();
  return ret;
 }
 return F_ExpNum();
}

//F->E|i
BiTree* F_ExpNum()
{
 BiTree* ret=new BiTree;
 ret->data="";
 if(isalnum(expr[pos]))
 {
  ret->data=expr[pos--];
  ret->lchild=ret->rchild=0;
  return ret;
 }
 if(pos<0)
 {
  cout<<"出错！未预期的结尾！"<<endl;
  longjmp(errjb,1);
 }
 if(expr[pos]=='+'||expr[pos]=='-'||expr[pos]=='*'||expr[pos]=='/')
 {
  return E_AddSub();
 }
 cout<<"出错！非法字符！"<<endl;
 longjmp(errjb,1);
}

void PreVisit(BiTree* BT)
{
 if(BT)
 {
  cout<<BT->data;
  PreVisit(BT->lchild);
  PreVisit(BT->rchild);
 }
}

int main()
{
 bool quit=false;
 do{
  if(setjmp(errjb)==0)
  {
   cout<<"请输入一个表达式(按'Q'或'q'退出):"<<endl;
   cin>>expr;
   if(expr[0]=='Q'||expr[0]=='q')
    quit=true;
   else
   {
    pos=expr.length()-1;
    BiTree* Root=E_AddSub();
    if((int)expr[pos]>0)
    {
     cout<<"出错！冗余的字符！"<<endl;
     longjmp(errjb,1);
    }
    cout<<"该后缀表达式的前缀表达式如下："<<endl;
    PreVisit(Root);
    cout<<endl;
   }
  }
  else
  {
   cout<<"您输入的字符串不是后缀表达式！"<<endl;
  }
 }while(!quit);
 return 0;
}