Evaluates elementary arithmetic expressions by converting from infix to post-fix notation

arithmetic.cpp

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

using namespace std;

// Returns true if left has greater than or equal to arithmetic precedence than right
bool has_precedence(const char& left, const char& right)
{
	if (left == '*' || left == '/')
	{
		switch (right)
		{
		case '*':
		case '/':
		case '-':
		case '+':
			return true;
		}
	}

	if (left == '+' || left == '-')
	{
		switch (right)
		{
		case '+':
		case '-':
			return true;
		}
	}

	return false;
}

string::size_type find_any(const string& word, const string& delimiters)
{
	string::size_type position = INT_MAX;
	for (char c : delimiters)
	{
		string::size_type tmp = word.find(c);
		if (c != string::npos && tmp < position)
			position = tmp;
	}

	if (position == INT_MAX)
	{
		return string::npos;
	}
	
	return position;
}

vector<string> split(string word, string delimiters)
{
	vector<string> result;
	std::string::size_type n;

	while ((n = find_any(word, delimiters)) != string::npos)
	{
		string term = word.substr(0, n);
		if (!term.empty())
		{
			result.push_back(term);
		}

		result.push_back(word.substr(n, 1));
		word = word.substr(n+1);
	}

	if (!word.empty())
	{
		result.push_back(word);
	}

	return result;
}

vector<string> to_postfix(const string& input)
{
	vector<string> expression;
	stack<string> operators;

	vector<string> tokens = split(input, "()^*/+-");
	
	// don't use strings use vector strings
	std::for_each(tokens.begin(), tokens.end(), 
		[&] (string token)
		{
			
			token.erase(remove_if(token.begin(), token.end(), isspace), token.end());

			if (token.length() > 1)
			{ 
				// assume it's some integer
				expression.push_back(token);
			}
			else if (token.length() == 1)
			{
				char c = token[0];

				switch (c)
				{
				case ' ':
					break;

				case '(':
					operators.push(token);
					break;

				case ')':

					if (operators.empty())
						break;

					while (operators.top() != "(")
					{
						expression.push_back(operators.top());
						operators.pop();
					}
					// pop the (
					operators.pop();

					break;

				case '^':
				case '*':
				case '/':
				case '+':
				case '-':

					while (!operators.empty() && has_precedence(operators.top()[0], c))
					{
						expression.push_back(operators.top());
						operators.pop();
					}

					operators.push(token);

					break;

				default:
					if (isdigit(c))
						expression.push_back(token);
					break;
				}
			}
		});

	while (!operators.empty())
	{ 
		if (operators.top() != "(")
		{
			expression.push_back(operators.top());
		}
		operators.pop();
	}

	return expression;
}

double evaluate(vector<string> postfix)
{
	// would be better to throw an exception
	if (postfix.empty())
		return 0;
	
	stack<double> numbers;

	std::for_each(postfix.begin(), postfix.end(),
		[&](const string& token)
	{
		double a;
		static stringstream str;
		str.clear();
		// we can simplify our parsing since expression will not contain ()'s
		if (token.length() > 1)
		{

			str << token;
			str >> a;
			numbers.push(a);
		}
		else if (isdigit(token[0]))
		{
			str << token;
			str >> a;
			numbers.push(a);
		}
		else if (token.length() == 1)
		{
			char op = token[0];
			double b;

			b = numbers.top();
			numbers.pop();
			a = numbers.top();
			numbers.pop();

			switch (op)
			{
			case '^':
				numbers.push(pow(a, b));
				break;

			case '*':
				numbers.push(a * b);
				break;

			case '/':
				numbers.push(a / b);
				break;

			case '+':
				numbers.push(a + b);
				break;

			case '-':
				numbers.push(a - b);
				break;

			default:
				// unsupported operation
				break;
			}
		}
	});

	return numbers.top();
}

void print_vector(const vector<string>& vec)
{
	for (string str : vec)
	{
		cout << str << " ";
	}
	cout << endl;
}

int main()
{
	string input;
	vector<string> postfix;

	cout << "Enter arithmetic expression: " << endl;
	cin >> ws >> input;
	postfix = to_postfix(input);
	cout << "In postfix form: ";
	print_vector(postfix);
	cout << "Evaluated: " << evaluate(postfix) << endl;

	return 0;
}