#include "stdafx.h"

#include <iostream>

#include <stack>

#include <string>

class expr_tree

{

	struct base_node

	{

		char c;

		base_node * lc, *rc;

		base_node() {}

		base_node(char c)

			: c(c)

			, lc(nullptr)

			, rc(nullptr)

		{

		}

	} * root;

protected:

	void parse_expr(std::string str);

	void proorder_print(base_node * n);

	void inorder_print(base_node * n);

	void postorder_print(base_node * n);

	void destory(base_node * & n);

	double eval(base_node * n);

public:

	void show();

	expr_tree(std::string str)

	{

		parse_expr(str);

	}

	~expr_tree()

	{

		destory(this->root);

	}

};

void expr_tree::parse_expr(std::string str)

{

	std::stack<base_node *> stack_node;

	for (auto c : str)

	{

		base_node * node = new base_node(c);

		if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z')

			stack_node.push(node);

		else if (c == '+' || c == '-' || c == '*' || c == '/')

		{

			if (!stack_node.empty())

			{

				node->rc = stack_node.top();

				stack_node.pop();

			}

			if (!stack_node.empty())

			{

				node->lc = stack_node.top();

				stack_node.pop();

			}

			stack_node.push(node);

		}

		else

		{

			std::cout << "表达式有误!" << std::endl;

			exit(1);

		}

	}

	root = stack_node.top();

	while (!stack_node.empty())

		stack_node.pop();

}

void expr_tree::proorder_print(base_node * n)

{

	if (n)

	{

		std::cout << n->c;

		proorder_print(n->lc);

		proorder_print(n->rc);

	}

}

void expr_tree::inorder_print(base_node * n)

{

	if (n)

	{

		if (n->c >= '0' && n->c <= '9')

			std::cout << n->c;

		else

		{

			std::cout << '(';

			inorder_print(n->lc);

			std::cout << ' ' << n->c << ' ';

			inorder_print(n->rc);

			std::cout << ')';

		}

	}

}

void expr_tree::postorder_print(base_node * n)

{

	if (n)

	{

		postorder_print(n->lc);

		postorder_print(n->rc);

		std::cout << n->c;

	}

}

void expr_tree::show()

{

	std::cout << "前缀表达式:" << std::endl;

	proorder_print(this->root);

	std::cout << std::endl;

	std::cout << "中缀表达式:" << std::endl;

	inorder_print(this->root);

	std::cout << " = " << eval(this->root) << std::endl;

	std::cout << "后缀表达式:" << std::endl;

	postorder_print(this->root);

	std::cout << std::endl;

}

double expr_tree::eval(base_node * n)

{

	switch (n->c)

	{

	case '+': return eval(n->lc) + eval(n->rc);

	case '-': return eval(n->lc) - eval(n->rc);

	case '*': return eval(n->lc) * eval(n->rc);

	case '/': return eval(n->lc) / eval(n->rc);

	default: return n->c - '0';

	}

}

void expr_tree::destory(base_node * & root)

{

	if (root != nullptr)

	{

		destory(root->lc);

		destory(root->rc);

		delete root;

	}

}

int main()

{

	std::string str = "23+456+**";

	expr_tree res(str);

	res.show();

	return 0;

}