Prefix expressions

Description:
You are given a prefix expression. Write a program to evaluate it.
Input sample:
The first argument will be an input file with one prefix expression per line. e.g.

* + 2 3 4

Your program has to read this and insert it into any data structure you like. Traverse that data structure and evaluate the prefix expression. Each token is delimited by a whitespace. You may assume that the only valid operators appearing in test data are ‘+’,’*’ and ‘/’
Output sample:
Print to stdout, the output of the prefix expression, one per line. e.g.

20

My solution

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <algorithm>

void Tokenize(const std::string& str, 
			  std::vector<std::string>& tokens,
			  const std::string& delimiters = " ") {
	std::string::size_type lastPos = str.find_first_not_of(delimiters, 0);
	std::string::size_type pos     = str.find_first_of(delimiters, lastPos);
	while (std::string::npos != pos || std::string::npos != lastPos){
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        lastPos = str.find_first_not_of(delimiters, pos);
        pos = str.find_first_of(delimiters, lastPos);
    }
}

int string_to_int(std::string const &val) {
	std::istringstream istr(val);
	int returnVal;
	istr >> returnVal;
	return returnVal;
}

void evaluate_prefix_expression( std::string &expr) {
	std::stack<int> operand_stack;
	std::string operators = "+*/-";
	//std::reverse(expr.begin(), expr.end());
	std::vector<std::string> tokens;
	Tokenize(expr,tokens);
	for ( std::vector<std::string>::reverse_iterator itr = tokens.rbegin();
		itr != tokens.rend(); ++itr) {
			if ( operators.find(*itr) == std::string::npos) {
				operand_stack.push(string_to_int(*itr));
			}
			if ( operators.find(*itr) != std::string::npos){
				int t1 = operand_stack.top(); operand_stack.pop();
				int t2 = operand_stack.top(); operand_stack.pop();
				if ( *itr == "+") {
					operand_stack.push(t1 + t2 );
				} else if ( *itr == "*" ) {
					operand_stack.push(t1 * t2 );
				} else if ( *itr == "/" ) {
					operand_stack.push(t1 / t2 );
				} else if ( *itr == "-" ) {
					operand_stack.push(t1 - t2 );
				}

			}
	}
	std::cout << operand_stack.top() << std::endl;
}
int main( int argc, char **argv) {
    std::ifstream inpFile(argv[1]);
    if ( inpFile.peek() == EOF ){
        return -1;
	} 
    std::string line; 
    if (inpFile.is_open()) {
        while (! inpFile.eof() ) {               
            std::getline (inpFile,line);
			if ( !line.empty()) {
				evaluate_prefix_expression(line);
			}
        }
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s