UVa 12392 - Guess the Numbers

// UVa 12392 - Guess the Numbers

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;

map<char, int> val;

struct oper {
	char sign;
	int prio;
};

int calc(int a, int b, char sign) {
	if (sign == '+')
		return a + b;
	else if (sign == '-')
		return a - b;
	else if (sign == '*')
		return a * b;
	return 0000;
}

int eval(string s) {
	stack<oper> operators;
	stack<int> operands;
	int base_priority = 0;

	// loop each character
	for (int i = 0; i < s.length(); i++) {
		char ch = s[i];

		// see if it's a variable
		if ('a' <= ch && ch <= 'z') {
			operands.push(val[ch]);
			continue;
		}
		// brackets
		if (ch == '(') {
			base_priority += 10;
			continue;
		}
		if (ch == ')') {
			base_priority -= 10;
			continue;
		}

		// it's an operator, see the priority
		int priority = base_priority;
		if (ch == '+')
			priority += 1;
		else if (ch == '-')
			priority += 1;
		else if (ch == '*')
			priority += 2;

		// check for previous operators with more priority (or equal priority)
		while (!operators.empty() && operators.top().prio >= priority) {

			// get and remove operands and operator on top of stacks
			int b = operands.top();
			operands.pop();
			int a = operands.top();
			operands.pop();
			char sign = operators.top().sign;
			operators.pop();

			// do the operation and place result on stack
			int c = calc(a, b, sign);
			operands.push(c);
		}
		operators.push( { ch, priority });
	}

	// same 'while' that before but without the priority condition
	while (!operators.empty()) {

		// get and remove operands and operator on top of stacks
		int b = operands.top();
		operands.pop();
		int a = operands.top();
		operands.pop();
		char sign = operators.top().sign;
		operators.pop();

		// do the operation and place result on stack
		int c = calc(a, b, sign);
		operands.push(c);
	}

	// result will be on stack
	return operands.top();
}

int main() {
	while (true) {
		int n, m, v[5];
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> v[i];
		cin >> m;
		if (n == 0 && m == 0)
			break;
		string expression;
		cin >> expression;
		int c = 0;
		char var[5];
		for (int i = 0; i < expression.length(); i++)
			if ('a' <= expression[i] && expression[i] <= 'z')
				var[c++] = expression[i];

		bool found = false;
		sort(v, v + n);
		do {
			string exp = expression;
			for (int i = 0; i < n; i++)
				val[var[i]] = v[i];
			if (eval(exp) == m) {
				found = true;
				break;
			}
		} while (next_permutation(v, v + n));

		if (found)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}