《中缀表达式表示成二叉树》由会员分享，可在线阅读，更多相关《中缀表达式表示成二叉树（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() con
2、st;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:
3、pop()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 stackL
4、isttopIndex;template bool stack:empty() constreturn topIndex = -1;template bool stack:full() const return 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; s
6、witch(op)case +: case -: inputPrecedence = 1; stackPrecedence = 1; break;case *: case %: case /: inputPrecedence = 2; stackPrecedence = 2; break;case : inputPrecedence = 4; stackPrecedence = 3; break;case (: inputPrecedence = 5; stackPrecedence = -1; break;case ): inputPrecedence = 0; stackPrecedenc
7、e = 0; break;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(con
8、st expressionSymbol& op);bool isOperator(char ch) const;/ ch is one of +,-,*,/,%,;void infix2Postfix:outputHigherOrEqual(const expressionSymbol& op)expressionSymbol op2;while(!operatorStack.empty() &(op2 = operatorStack.top() = op)operatorStack.pop();postfixExpression += op2.getOp();postfixExpressio
9、n += ;bool infix2Postfix:isOperator(char ch) constreturn ch = + | ch = - | ch = * | ch = % | ch = / | ch = ;infix2Postfix:infix2Postfix()infix2Postfix:infix2Postfix(const string& infixExp):infixExpression(infixExp)void infix2Postfix:setInfixExp(const string& infixExp)infixExpression = infixExp;postf
10、ixExpression = ;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 = expressionSymbol
11、(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 (rank != 1
12、)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;#include#include#include#includestack.husing namespace std;
