/////////////////////////////////////////////////////////////////////////////////////////
//
//Infix2PreifxorPostFix.cpp
//姓名：
//学号：
//院系：
//要求：构建一个表达式树，当输入中缀表达式时，输出并打印其前缀及后缀表达式
//实现：构造一个标准的表达式树的类，它涵盖先序、中序、后序遍历操作，通过不同顺序的打印操作来实现转换操作；
// 相对于使用栈来进行转换，免去了中缀转成前缀时进行的逆序操作
///////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
//定义树的结点信息
struct BinaryNode
{
string data;
BinaryNode* left;
BinaryNode* right;
BinaryNode(string s = "", BinaryNode *leftNode = NULL, BinaryNode *rightNode = NULL)
:data(s), left(leftNode), right(rightNode){}
};
//定义表达式树
class ExpressionTree {
public:
ExpressionTree();
ExpressionTree(ExpressionTree & tree);
~ExpressionTree();
void SetRoot(BinaryNode *op);
BinaryNode *GetRoot();
vector<string> PreOrder();
vector<string> InOrder();
vector<string> PostOrder();
private:
BinaryNode *root;
void Release(BinaryNode* &node);
void PrePrint(BinaryNode* node, int depth, vector<string>& sample);
void InPrint(BinaryNode* node, int depth, vector<string>& sample);
void PostPrint(BinaryNode* node, int depth, vector<string>& sample);
void PrintDepth(const string &s, const int depth);
};
ExpressionTree::ExpressionTree()
{
root = NULL;
}
ExpressionTree::ExpressionTree(ExpressionTree & tree)
{
root = tree.GetRoot();
}
ExpressionTree::~ExpressionTree()
{
Release(root);
}
void ExpressionTree::SetRoot(BinaryNode* op)
{
root = op;
}
BinaryNode* ExpressionTree::GetRoot()
{
return root;
}
vector<string> ExpressionTree::PreOrder()
{
vector<string> preVec;
cout << "Preorder Traversal（先序遍历）:\n";
PrePrint(root, 0, preVec);
return preVec;
}
vector<string> ExpressionTree::InOrder()
{
vector<string> inVec;
cout << "Inorder Traversal（中序遍历）:\n";
InPrint(root, 0, inVec);
return inVec;
}
vector<string> ExpressionTree::PostOrder()
{
vector<string> postVec;
cout << "Postorder Traversal（后序遍历）:\n";
PostPrint(root, 0, postVec);
return postVec;
}
void ExpressionTree::Release(BinaryNode *&node)
{
if (!node)
return;
if (node->left)
{
Release(node->left);
}
if (node->right)
{
Release(node->right);
}
delete node;
node = NULL;
}
void ExpressionTree::PrePrint(BinaryNode* node, int depth, vector<string> &sample)
{
if (node)
{
PrintDepth(node->data, depth);
sample.push_back(node->data);
if (node->left)
PrePrint(node->left, depth + 1, sample);
if (node->right)
PrePrint(node->right, depth + 1, sample);
}
}
void ExpressionTree::InPrint(BinaryNode* node, int depth, vector<string> &sample)
{
if (node)
{
if (node->left)
InPrint(node->left, depth + 1, sample);
PrintDepth(node->data, depth);
sample.push_back(node->data);
if (node->right)
InPrint(node->right, depth + 1, sample);
}
}
void ExpressionTree::PostPrint(BinaryNode* node, int depth, vector<string> &sample)
{
if (node)
{
if (node->left)
PostPrint(node->left, depth + 1, sample);
if (node->right)
PostPrint(node->right, depth + 1, sample);
PrintDepth(node->data, depth);
sample.push_back(node->data);
}
}
void ExpressionTree::PrintDepth(const string &s, const int depth)
{
string blank = " ";
for (int i = 0; i < depth; ++i)
cout << blank;
cout << s << endl;
}
// 判断是否为运算符
bool isOperator(const char op)
{
return op == '+' || op == '-' || op == '*' || op == '/' || op == '(' || op == ')';
};
bool isOperator(const string s)
{
return s == "+" || s == "-" || s == "*" || s == "/" || s == "(" || s == ")";
}
// 求运算符优先级
int priority(const char op)
{
switch (op)
{
case '#':
return 0;
case '）':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
case '（':
return 4;
default:
return 0;
}
};
//从输入表达式得到操作数和操作符
vector<string>GetExpression(const string Exp)
{
vector<string> sample;
int lastOperator = 0;
for (int i = 0; i < Exp.length(); ++i)
{
if (isOperator(Exp[i]))
{
string operand = Exp.substr(lastOperator, i - lastOperator);
if (operand != "")
{
sample.push_back(operand);
}
lastOperator = i + 1;
sample.push_back(Exp.substr(i, 1));
}
else if (i == Exp.length() - 1)
{
sample.push_back(Exp.substr(lastOperator, i + 1 - lastOperator));
}
}
return sample;
};
// 把中缀表达式转换为后缀表达式
vector<string> InFix2PostFix(const string InFix)
{
vector<string> InFixVector = GetExpression(InFix);
vector<string> PostFix;
stack<string> myStack;
for (int i = 0; i < InFix.size(); ++i) {
string topString;
if (!myStack.empty())
topString = myStack.top();
if (InFixVector[i] == "(")
myStack.push(InFixVector[i]);
else if (InFixVector[i] == "*" || InFixVector[i] == "/") {
while (1) {
if (!myStack.empty() && (topString == "*" || topString == "/")) {
PostFix.push_back(topString);
myStack.pop();
if (!myStack.empty())
topString = myStack.top();
}
else {
myStack.push(InFixVector[i]);
break;
}
}
}
else if (InFixVector[i] == "+" || InFixVector[i] == "-") {
while (!myStack.empty()) {
topString = myStack.top();
if (topString != "(") {
PostFix.push_back(topString);
myStack.pop();
}
else
break;
}
myStack.push(InFixVector[i]);
}
else if (InFixVector[i] == ")") {
while (topString != "(") {//seem like not safe
PostFix.push_back(topString);
myStack.pop();
if (!myStack.empty())
topString = myStack.top();
else {
cout << "error “)” with no “(” matched!" << endl;
break;
}
}
myStack.pop(); //pop the {
}
else {//operand
PostFix.push_back(InFixVector[i]);
}
}
while (!myStack.empty()) {
PostFix.push_back(myStack.top());
myStack.pop();
}
return PostFix;
};
//转换成表达式树
BinaryNode* getExpTreeFromPostVec(const vector<string> &PostFix)
{
if (PostFix.size() == 0) return NULL;
//transform PostFixVector to an expression tree
stack<BinaryNode*> stack4tree;
for (int j = 0; j < PostFix.size(); ++j) {
if (!isOperator(PostFix[j])) {
BinaryNode* node = new BinaryNode;
node->data = PostFix[j];
stack4tree.push(node);
}
else {
BinaryNode* father = new BinaryNode;
father->data = PostFix[j];
father->right = stack4tree.top();
stack4tree.pop();
father->left = stack4tree.top();
stack4tree.pop();
stack4tree.push(father);
}
}
return stack4tree.top();
}
//打印树
void PrintTree(const vector<string>& sample)
{
for (int i = 0; i < sample.size(); ++i)
cout << sample[i] << " ";
cout << "\n";
}
int main()
{
string InFixExp;
cout << "请输入中缀表达式，如1+2*3+4/5： " << endl;
cin >> InFixExp;
ExpressionTree tree;
tree.SetRoot(getExpTreeFromPostVec(InFix2PostFix(InFixExp)));
vector<string> sample = tree.PreOrder();
cout << "前缀表达式:";
PrintTree(sample);
sample = tree.InOrder();
cout << "中缀表达式:";
PrintTree(sample);
sample = tree.PostOrder();
cout << "后缀表达式:";
PrintTree(sample);
system("pause");
return 0;
}
