reverse_polish.cc

#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <stack>
#include <vector>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>


struct Node {
	virtual int32_t value(){return 0;}
	virtual void print(){}
	virtual ~Node(){}
};


struct OpNode : Node {
	char op;
	Node *left, *right;

	OpNode(char o, Node* l, Node* r) : 
		op(o),
		left(l),
		right(r) {}
	virtual ~OpNode() {
		delete left;
		delete right;
	}

	virtual int32_t value() {
		auto l = left->value();
		auto r = right->value();
		int32_t ret;
		switch(op) {
		case '+':
			ret = l + r;
			break;
		case '-':
			ret = l - r;
			break;
		case '*':
			ret = l * r;
			break;
		case '/':
			ret = l / r;
			break;
		default:
			ret = 0;
			break;
		}
		return ret;
	}

	virtual void print() {
		left->print();
		right->print();
		std::cout << op << ' ';
	}
};


struct ValNode : Node {
	int32_t val;

	ValNode(int32_t v) : val(v) {}
	virtual ~ValNode(){}

	virtual int32_t value() {
		return val;
	}

	virtual void print() {
		std::cout << val << ' ';
	}
};


bool isOperator(char *e) {
	using std::strcmp;
	return strcmp(e, "+") == 0 || strcmp(e, "-") == 0 || strcmp(e, "*") == 0 || strcmp(e, "/") == 0;
}

bool isOperator(std::string e) {
	return e == "+" || e == "-" || e == "*" || e == "/";
}

Node *makeTree(std::vector<std::string> vc) {
	std::unique_ptr<std::stack<Node*>> st(new std::stack<Node*>);

	for(auto e : vc) {
		if(isOperator(e)) {
			auto right = st->top();
			st->pop();
			auto left = st->top();
			st->pop();
			auto node = new OpNode(e[0], left, right);
			st->push(node);
		} else {
			std::stringstream ss;
			ss << e;
			int32_t v;
			ss >> v;
			auto node = new ValNode(v);
			st->push(node);
		}
	}

	return st->top();
}

Node *makeTree(int n, char **arr) {
	std::unique_ptr<std::stack<Node*>> st(new std::stack<Node*>);

	for(int i = 0; i < n; i++) {
		auto e = arr[i];
		if(isOperator(e)) {
			auto right = st->top();
			st->pop();
			auto left = st->top();
			st->pop();
			auto node = new OpNode(e[0], left, right);
			st->push(node);
		} else {
			std::stringstream ss;
			ss << e;
			int32_t v;
			ss >> v;
			auto node = new ValNode(v);
			st->push(node);
		}
	}
	return st->top();
}

auto main(int argc, char **argv) -> int {
	Node *tree;
	if(argc > 1) {
		tree = makeTree(--argc, ++argv);
	} else {
		std::unique_ptr<std::vector<std::string>> vc(new std::vector<std::string>);
		std::string str;
		getline(std::cin, str);
		boost::algorithm::split(*vc, str, boost::is_any_of(" "));
        
		if(vc->size() == 0 || vc->at(0).length() < 1) {
			std::cerr << "Input Error" << std::endl;
			exit(EXIT_FAILURE);
		}

		tree = makeTree(*vc);
	}

	tree->print();
	std::cout << std::endl;

	std::cout << tree->value() << std::endl;
	exit(EXIT_SUCCESS);
}