中缀表达式表示成二叉树.doc
文本预览下载声明
将一个中缀表达式表示成二叉树的形式，相关提示如下：
（1） 基本思路： 中缀先转换成后缀，然后再表示成二叉树。这样做起来要方便的多；
（2） 打印二叉树时，可以用课件上的逆时针旋转90度打印方式。
#includeiostream
#includestring
#included_except.h
using namespace std;
#ifndef STACK
#define STACK
const MAXSTACKSIZE=50;
templatetypename T
class stack //有限栈
{
public:
stack();
void push(const T item);
void pop();
T top();
const T top() const;
bool empty() const;
bool full() const;
int size() const;
private:
T stackList[MAXSTACKSIZE];
int topIndex;
};
template typename T
stackT::stack(){topIndex=-1;}
template typename T
void stackT::push(const T item)
{
if(full())
throw underflowError(miniStack top():stack empty);//exit(1);
topIndex++;
stackList[topIndex]=item;
}
template typename T
void stackT::pop()
{
if (empty())
throw underflowError(miniStack top(): stack empty);
topIndex--;
}
template typename T
T stackT::top()
{
if (empty()) throw underflowError(miniStack top(): stack empty);
return stackList[topIndex];
}
template typename T
const T stackT::top() const
{
if (empty()) throw underflowError(miniStack top(): stack empty);
return stackList[topIndex];
}
template typename T
bool stackT::empty() const
{
return topIndex == -1;
}
template typename T
bool stackT::full() const
{
return topIndex==MAXSTACKSIZE-1;
}
template typename T
int stackT::size() const
{
return topIndex+1;
}
#endif
#includestring
#includestack.h
using namespace std;
class expressionSymbol
{
public:
expressionSymbol();
expressionSymbol(char ch);
friend bool operator= (const expressionSymbol left, const expressionSymbol right )
{
return left.stackPrecedence = right.inputPrecedence;
}
char getOp() const;
private:
char op;
int inputPrecedence;
int stackPrecedence;
};
expressionSymbol::expressionSymbol()
{}
expressionSymbol::expressionSymbol(char ch)
{ op = ch;
switch(op)
{ case +:
case -: inputPrecedence = 1;
stackPrecedence = 1; break;
case *:
case %:
case /: inputPrecedence
显示全部