后序遍历解决四则运算的输出
VC++利用二叉树的后序遍历桉顺序输出每一步的运算结果/* 二叉树后序遍历--源代码及关键源代码注解如下：*/
// FileName: treemain.cpp .
#include <iostream>
#include <string>
#include <stack>
#include "tree.h"
/********** Checks if expression is ok *********/
bool isok(string exp)
{
char check;
int error=0;
int lb=0;
int rb=0;
for(int m=0;m < exp.size(); m++)
{
check = exp[m];
if(IsOperand(check))
{
}
else if(IsOperator(check))
{
if(check == ')')
{
rb++;
if(IsOperator(exp[m+1]) && (exp[m+1]=='+' || exp[m+1]=='-' || exp[m+1]=='*'
|| exp[m+1]=='/' || exp[m+1]=='^' || exp[m+1]==')'))
{
m++;
if(exp[m] == ')')
rb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
else if(check == '(')
{
lb++;
if(IsOperator(exp[m+1]) && exp[m+1] =='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
else
{
if(IsOperator(exp[m+1]) && exp[m+1] == '(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
}
else
error++;
}
if(error == 0 && lb==rb)
return(true);
else
return(false);
}
/*****************************************/
/*
void main()
{
binary_tree etree;
stack<binary_tree> NodeStack;
stack<char> OpStack;
string infix;
char choice = 'y';
char c;
while(choice == 'y' || choice == 'Y')
{
cout << "\n\nIntroduce the Expression (no spaces): ";
cin >> infix;
cout << "----------------------------------------------" << endl;
cout << "Expression: " << infix << endl;
if(isok(infix))
{
for(int i=0; i < infix.size(); i++)
{
c = infix[i];
if(IsOperand(c)) //if operand, create tree and push into NodeStack
{
string tempstring;
tempstring = tempstring + c;
if(i+1 < infix.size() && IsOperand(infix[i+1]))
{
while(i+1 < infix.size() && IsOperand(infix[i+1]))
{
tempstring = tempstring + infix[++i];
}
}
binary_tree temp;
temp.root = build_node(tempstring);
NodeStack.push(temp);
}
//Else if Operator, check precedence and push into OpStack
else if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^')
{
if(OpStack.empty())
OpStack.push(c);
else if(OpStack.top() == '(')
OpStack.push(c);
else if(TakesPrecedence(c, OpStack.top()))
OpStack.push(c);
else
{
while(!OpStack.empty() && TakesPrecedence(OpStack.top(), c))
{
binary_tree temp_tree;
string thisstring="";
thisstring = thisstring + OpStack.top();
OpStack.pop();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
etree.root = NULL;
}
OpStack.push(c);
}
}
else if(c == '(')
OpStack.push(c);
else if(c == ')')
{
while(OpStack.top() != '(')
{
binary_tree temp_tree;
string thisstring="";
thisstring = thisstring + OpStack.top();
OpStack.pop();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
etree.root = NULL;
}
OpStack.pop();
}
} // end of for loop
while(!OpStack.empty()) //While OpStack not empty, pop that stack
//and create tree
{
binary_tree temp_tree;
string thisstring="";
thisstring = thisstring + OpStack.top();
OpStack.pop();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
if(!OpStack.empty())
{
etree.root = NULL;
}
}
cout << "Postfix traversal: ";
etree.print();
cout << endl;
etree.evaluate();
cout << "Result: " << etree.root->data << endl;
cout << "----------------------------------------------" << endl;
cout << "\n\nRun Program again? Enter <y/n> : ";
cin >> choice;
}
}
} //end of main
*/
// FileName: tree.h By: Musawir Ali Shah
#ifndef _TREE_H_
#define _TREE_H_
#include <iostream>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;
// Overloaded function, checks a string for an operator
bool IsOperator(string mystring)
{
if(mystring == "-" || mystring == "+" || mystring == "/" || mystring == "*" || mystring == "^")
return(true);
else
return(false);
}
// Overloaded function, checks a character for an operator
bool IsOperator(char ops)
{
if(ops == '+' || ops == '-' || ops == '*' || ops == '/' || ops == '^' || ops == '(' || ops == ')')
return(true);
else
return(false);
}
//Binary Tree Definition and Implementation
class node_type
{
public:
string data;
node_type *left_child;
node_type *right_child;
node_type(string k)
{
data=k;
left_child = NULL;
right_child = NULL;
}
};
class binary_tree
{
public:
node_type *root;
void print(node_type *r); // Postfix traversal
binary_tree(void) { root = NULL;}
void print(void) {print (root);}
void evaluate()
{
evaluate(root);
}
void evaluate(node_type* prt) //recursive trea evaluation
{
if(IsOperator(prt->data) && !IsOperator(prt->left_child->data) && !IsOperator(prt->right_child->data))
{ if(prt->data==" ")
{
}
int num = 0;
int num1=atoi(prt->left_child->data.c_str());
int num2=atoi(prt->right_child->data.c_str());
if(prt->data == "+")
num = num1 + num2;
else if(prt->data == "-")
num = num1 - num2;
else if(prt->data == "*")
num = num1 * num2;
else if(prt->data == "/")
num = num1 / num2;
else if(prt->data == "^")
num = pow(num1,num2);
stringstream bob;
bob << num;
string suzzy(bob.str());
prt->data = suzzy;
prt->left_child = NULL;
prt->right_child = NULL;
}
else if(prt->left_child == NULL && prt->right_child == NULL);
else
{
evaluate(prt->left_child);
evaluate(prt->right_child);
evaluate(prt);
}
}
void clear_help(node_type* rt) // destructor
{
if( rt != NULL )
{
clear_help( rt->left_child);
clear_help( rt->right_child);
delete rt;
}
}
void clear()
{
clear_help(root);
}
};
node_type *build_node(string x) //build a new node for the tree
{
node_type *new_node;
new_node = new node_type(x);
return(new_node);
}
void binary_tree::print(node_type *p) //postfix traversal
{
if(p!=NULL)
{
print(p->left_child);
print(p->right_child);
cout<<p->data<<endl;
/*else if (p->data =="-")
cout<<a<<p->data<<b<<'='<<a-b<<endl;
else if (p->data =="/")
cout<<a<<p->data<<b<<'='<<a/b<<endl;
else if (p->data =="+")
cout<<a<<p->data<<b<<'='<<a+b<<endl;*/
}
}
bool IsOperand(char ch) //Checks for character to be an operand
{
if ((ch >= '0') && (ch <= '9'))
return true;
else
return false;
}
//Checks Precedence, returns true of A is higher precendence over B
bool TakesPrecedence(char OperatorA, char OperatorB)
{
if (OperatorA == '(')
return false;
else if (OperatorB == '(')
return false;
else if (OperatorB == ')')
return true;
else if ((OperatorA == '^') && (OperatorB == '^'))
return false;
else if (OperatorA == '^')
return true;
else if (OperatorB == '^')
return false;
else if ((OperatorA == '*') || (OperatorA == '/'))
return true;
else if ((OperatorB == '*') || (OperatorB == '/'))
return false;
else
return true;
}
//Creates a copy of a tree passes the roots of the 2 trees, r1 being the root of the tree to be copied to
// and r2 being the root of the tree being copied.
void copy(node_type *&r1, node_type *r2)
{
if(r2 == NULL)
r1 = NULL;
else
{
if(r1 == NULL)
{
r1 = build_node(r2->data);
copy(r1->left_child, r2->left_child);
copy(r1->right_child, r2->right_child);
}
else
{
r1 = build_node(r2->data);
copy(r1->left_child, r2->left_child);
copy(r1->right_child, r2->right_child);
}
}
}
#endif
