[c++][源代码]后缀表达式转化为前缀表达式

来源：百度文库 编辑：神马文学网 时间：2024/06/06 13:10:51
[C++][源代码]后缀表达式转化为前缀表达式
撰文/周翔
本人开源代码页：http://blog.csdn.net/hifrog/category/131301.aspx
功能：用户输入一个字符串，判断这个字符串是否是后缀表达式，并把它转化为前缀表达式，并显示。
原理：利用S属性文法的制导翻译生成语法树节点，其中该语法树为二叉树。非叶节点保存运算符，叶节点保存数字或变量。制导翻译公式请参考《编译原理》（高等教育出版社，陈意云著，2003年版）一书。笔者使用的产生式
加减二元运算的产生式：E->TE+|TE-|T
乘除二元运算的产生式：T->FT*|FT/|F
变量、数字、二元表达式的产生式：F->E|i
为了避免从左向右推导产生的歧意，笔者采用了从右向左推导。
其它特点：
1.程序能自动判断为什么不是后缀表达式；
2.代码长度不超过100行。
代码：
//*============= 代码: 周翔 ===============*//
#include
#include
#include
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<<"出错！未预期的结尾！"<longjmp(errjb,1);
}
if(expr[pos]==‘+‘||expr[pos]==‘-‘||expr[pos]==‘*‘||expr[pos]==‘/‘)
{
return E_AddSub();
}
cout<<"出错！非法字符！"<longjmp(errjb,1);
}
void PreVisit(BiTree* BT)
{
if(BT)
{
cout<data;
PreVisit(BT->lchild);
PreVisit(BT->rchild);
}
}
int main()
{
bool quit=false;
do{
if(setjmp(errjb)==0)
{
cout<<"请输入一个表达式(按‘Q‘或‘q‘退出):"<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<<"出错！冗余的字符！"<longjmp(errjb,1);
}
cout<<"该后缀表达式的前缀表达式如下："<PreVisit(Root);
cout<}
}
else
{
cout<<"您输入的字符串不是后缀表达式！"<}
}while(!quit);
return 0;
}
[c++][源代码]后缀表达式转化为前缀表达式 [c++][源代码]后缀表达式转化为前缀表达式 - 周翔的blog 正则表达式 OGNL表达式 Access表达式 正则表达式 正则表达式 Access表达式 正则表达式 正则表达式 正则表达式:正则表达式基础 词根、前缀、后缀大全 英语前缀后缀表 英语前缀、后缀 英文前缀后缀总 专家教您如何在C语言中巧用正则表达式 专家教您如何在C语言中巧用正则表达式 [精彩] 如何在C语言中巧用正则表达式 [精彩] 如何在C语言中巧用正则表达式 - ChinaUnix.net 视频格式转化为FLV (C 常用正则表达式,已封装为静态方法, 【正则表达式专题】正则表达式的应用 java正则表达式,js正则表达式 英语常见前缀后缀一览