10_43.cpp

前缀表达式用来说明显示输出树,接受输入的字符转化成为后缀二叉树

#include <iostream>
#include <string>

#include "int2pstf.h"
#include "d_rpn.h"

#include "d_tnodel.h"

using namespace std;

bool isOperator(char ch)
{
	return ch == '+' || ch == '-'
		|| ch == '*' || ch == '/';
}

void prefixOutput(tnode<char> *exp)
{
	if(exp != NULL)
	{
		cout << exp->nodeValue << " ";
		prefixOutput(exp->left);
		prefixOutput(exp->right);
	}

}

tnode<char> *buildExpTree(const string& pexp)
{
	string expression = pexp;
	tnode<char> *newnode,*root,*left,*right;
	stack<tnode<char>* > expstack;
	for(int i = 0;i < expression.length();i ++)
	{
		if(isalpha(expression[i]) || isdigit(expression[i]))
		{
			newnode = new tnode<char>(expression[i]);
			expstack.push(newnode);
		}
		else if(isOperator(expression[i]))
		{
			if (expstack.empty())
				throw  expressionError("postfixEval: Too many operators");
			
			right = expstack.top();
			expstack.pop();

			if (expstack.empty())
				throw  expressionError("postfixEval: Too many operators");
			
			left = expstack.top();
			expstack.pop();

			newnode = new tnode<char>(expression[i],left,right);
			expstack.push(newnode);
			root = newnode;
		}
	}
	return root;
}

void main()
{
	infix2Postfix iexp;
	
	string infixExp,postfixExp;

	tnode<char> *root;

	postfixEval pexp;

	cout << "Enter an infix expression: ";
	
	getline(cin,infixExp);

	iexp.setInfixExp(infixExp);

	postfixExp = iexp.postfix();

	cout<<"The postfix form is "<<postfixExp<<endl;

// (d)
	root = buildExpTree(postfixExp);

	displayTree(root,1);

// (e)
	cout << endl << "PrefixOutput: ";

	prefixOutput(root);

	cout << endl << endl;

// (f)
	string f1 = "(a+b)/c",f2 = "a+b*c/d+e/f*g";
	tnode<char> *tf1,*tf2;
	
	infix2Postfix if1,if2;

	postfixEval pf1,pf2;

	cout << f1 << endl << endl;
	cout << f2 << endl << endl;

	if1.setInfixExp(f1);
	if2.setInfixExp(f2);

	f1 = if1.postfix();
	f2 = if2.postfix();

	tf1 = buildExpTree(f1);
	tf2 = buildExpTree(f2);

	
	displayTree(tf1,1);
	cout << endl;
	postorderOutput(tf1);

	cout << endl << endl;
	
	displayTree(tf2,1);	
	cout << endl;
	postorderOutput(tf2);

	cout << endl << endl;
}