《中缀表达式表示成二叉树》由会员分享，可在线阅读，更多相关《中缀表达式表示成二叉树（8页珍藏版）》请在金锄头文库上搜索。
1、将一个中缀表达式表示成二叉树的形式，相关提示如下：(1) 基本思路： 中缀先转换成后缀，然后再表示成二叉树。这样做起来要方便的多(2) 打印二叉树时，可以用课件上的逆时针旋转90 度打印方式。 #include#include#included_except.husing namespace std;#ifndef STACK#define STACKconst MAXSTACKSIZE=50;templateclass stack /有限栈public:stack();void push(const T& item);void pop();T& top();const T& top() co
2、nst;bool empty() const;bool full() const;int size() const;private:T stackListMAXSTACKSIZE;int topIndex;template stack:stack()topIndex=-1;template void stack:push(const T& item)if(full()throw underflowError(miniStack top():stack empty);/exit(1);topIndex+;stackListtopIndex=item;template void stack:pop
3、()if (empty()throw underflowError(miniStack top(): stack empty);topIndex-;template T& stack:top()if (empty() throw underflowError(miniStack top(): stack empty); return stackListtopIndex;template const T& stack:top() constif (empty() throw underflowError(miniStack top(): stack empty); return stackLis
4、ttopIndex;template bool stack:empty() constreturn topIndex = -1;template bool stack:full() constreturn topIndex=MAXSTACKSIZE-1;template int stack:size() constreturn topIndex+1;#endif#include #includestack.husing namespace std;class expressionSymbolpublic:expressionSymbol(); expressionSymbol(char ch)
5、;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;
6、switch(op) case +:case -: inputPrecedence = 1;stackPrecedence = 1;break;case *:case %:case /: inputPrecedence = 2;stackPrecedence = 2;break;case A: inputPrecedence = 4;stackPrecedence = 3;break;case (: inputPrecedence = 5;stackPrecedence = -1;break;case ): inputPrecedence = 0;stackPrecedence = 0;bre
7、ak;char expressionSymbol:getOp() constreturn op;class infix2Postfixpublic:infix2Postfix();infix2Postfix(const string& infixExp); void setInfixExp(const string& infixExp); string postfix();private:string infixExpression;string postfixExpression;stack operatorStack;void outputHigherOrEqual(const expre
8、ssionSymbol& op); bool isOperator(char ch) const;/ ch is one of +,-,*,7,%,人;void infix2Postfix:outputHigherOrEqual(const expressionSymbol& op) expressionSymbol op2;while(!operatorStack.empty() &(op2 = operatorStack.top() = op)operatorStack.pop();postfixExpression += op2.getOp();postfixExpression +=
9、;bool infix2Postfix:isOperator(char ch) constreturn ch = + | ch = - | ch = * |ch = % II ch = / II ch = A;infix2Postfix:infix2Postfix()infix2Postfix:infix2Postfix(const string& infixExp): infixExpression(infixExp)void infix2Postfix:setInfixExp(const string& infixExp)infixExpression = infixExp; postfi
10、xExpression = ;string infix2Postfix:postfix()expressionSymbol op;int rank = 0, i;char ch;for (i=0; i 1)throw expressionError(infix2Postfix:Operator expected); else if (isOperator(ch) | ch = ()if (ch != () rank-;if (rank 0)throw expressionError(infix2Postfix:Operand expected); elseop = expressionSymb
11、ol(ch); outputHigherOrEqual(op); operatorStack.push(op);else if (ch = )op = expressionSymbol(ch); outputHigherOrEqual(op); if(operatorStack.empty()throw expressionError(infix2Postfix: Missing (); elseoperatorStack.pop();else if (!isspace(ch)throw expressionError(infix2Postfix: Invalid input);if (ran
12、k != 1)throw expressionError(infix2Postfix: Operand expected);elsewhile (!operatorStack.empty()op = operatorStack.top(); operatorStack.pop(); if (op.getOp() = ()throw expressionError(infix2Postfix: Missing ); elsepostfixExpression += op.getOp(); /postfixExpression += ;return postfixExpression;#inclu
13、de#include#include#includestack.husing namespace std;class tnodepublic:char nodeValue;tnode *left, *right;tnode()tnode (const char& item, tnode *lptr = NULL,tnode *rptr = NULL): nodeValue(item), left(lptr), right(rptr) tnode* buildtree(string str); int depth(tnode *root); void print(tnode *node_ptr, int depth); ;/根据后缀表达式生成二叉树tnode* tnode:buildtree(string n)tnode *ptr;stack nodeStack;char c;int
