pex11_8.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

#include "treenode.h"
#include "treelib.h"
#include "treeprnt.h"
#include "treescan.h"

// build an expression tree from the prefix expression
// contained in the NULL-terminated string exp. the operands
// are single letter identifiers in the range 'a' .. 'z' and
// the operands are selected from the characters '+', '-',
// '*' and '/'
TreeNode<char> *BuildExpTree (char * & exp)
{
	// newnode is the address of the subtree we are building
	TreeNode<char> *newnode = NULL, *lptr, *rptr;
	char token;

	// if we have not reached the end of the string, keep
	// building the tree
	if (*exp)
	{
		// skip blanks and tabs in the expression
		while (*exp == ' ' || *exp == '\t')
			exp++;
		token = *exp++;
		// extract the current stoken and increment exp
		// see if the token is an operator or an operand
		if (token == '+' || token == '-' || token == '*' || token == '/')
		{
			// current token is an operator. read the input stream
			// and build the two operands (left and right subtrees of
			// the operator)
			lptr = BuildExpTree(exp);
			rptr = BuildExpTree(exp);
			// create the node now that the data and pointers are defined
			newnode = new TreeNode<char> (token,lptr,rptr);
		}
		else // must be an operand
			newnode = new TreeNode<char> (token);	// leaf node
	}
	return newnode;
}

// print the operator or operand in an expression
// tree node
void PrintExpNode(char& item)
{
	cout << item << "  ";
}

void main (void)
{
	// root of the expression tree
	TreeNode<char> *exproot;
	// prefix expression read into string
	char expression[80], *exp = expression;
	
	// read the prefix expression and build the tree
	cout << "Enter the expression: ";
	cin.getline(expression,80,'\n');
	exproot = BuildExpTree(exp);

	// print the expression tree upright
	PrintVTree(exproot, 1, 50);
	cout << endl << endl;

	// print the infix form of the expression
	cout << "Infix form: ";
	Inorder(exproot,PrintExpNode);
	cout << endl;

	// print the postfix (RPN) form of the expression
	cout << "Postfix form: ";
	Postorder(exproot,PrintExpNode);
	cout << endl;
	
}

/*
<Run>

Enter the expression: +a+/ *bcd* /efg
                        +

            a                       +

                              /           *

                           *     d     /     g

                         b   c       e   f

Infix form: a  +  b  *  c  /  d  +  e  /  f  *  g
Postfix form: a  b  c  *  d  /  e  f  /  g  *  +  +
*/