将中缀表达式转换为后缀表达式-C++程序[一].doc
文本预览下载声明
PAGE
PAGE 1
5 将中缀表达式转换为后缀表达式
【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。
例如： a*(x+y)/(b-x) 转换后得： a x y + * b x - /
【数据结构】
定义一个暂时存放运算符的转换工作栈opst。
中缀表达式字符串char *infix;
后缀表达式字符串char *postfix;
【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。
从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：
数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；
左括号，进栈，直到遇见相配的右括号，才出栈；
右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；
对于运算符，分两种情况处理：
该运算符的优先级大于栈顶符号的优先级，则入栈；
若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。
说明：自行设计运算符优先级的表示。
【主要代码】
#includeiostream.h
#includeassert.h
#includemath.h
#includestring.h
const int stackIncreament=0;
class opst
{
public:
opst(int sz=50)
{
maxSize=sz;
top=-1;
elements=new char[maxSize];
assert(elements!=NULL);
}
~opst(){delete[]elements;}
bool IsEmpty(){return (top==-1)?true:false;}
bool IsFull(){return (top==maxSize-1)?true:false;}
void Push( char x);
bool Pop(char x);
bool getTop(char x);
int getSize()const{return top+1;}
void MakeEmpty(){top=-1;}
void input();
void Convert();
friend ostream operator(ostream os,opst s);
private:
char *elements;
int top;
int maxSize;
void overflowProcess();
};
void opst::overflowProcess()//溢出处理
{
char *newArray=new char[maxSize+stackIncreament];
for(int i=0;i=top;i++) newArray[i]=elements[i];
maxSize=maxSize+stackIncreament;
delete [] elements;
elements=newArray;
}
void opst::Push(char x)
{
if(IsFull()==true) overflowProcess();
elements[++top]=x;
}
bool opst::Pop( char x)
{
if(IsEmpty()==true) return false;
x=elements[top--];
return true;
}
bool opst::getTop(char x)
{
if(IsEmpty()==true)return false;
x=elements[top];
return true;
}
ostream operator(ostream os,opst s)
{
ostop==s.topendl;
for(int i=0;i=s.top;i++)
oss.elements[i];
return os;
}
void opst::input()
{
char ch[20];
cout请输入中缀表达式(括号不能省略)：endl;
cin.getline(ch,20);
int i=0;
while(ch[i]!=\0)
{this-Push(ch[i]);i++;}
ch[i]=#;
}
bool isdigit(char x)
{
if((x=ax=z)||(x=Ax=Z)||(x=0x=9))
return true;
else return false;
}
in
显示全部