Soptq

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <stdexcept>
#include <cmath>

#define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '%' || c == '^')
#define is_left_operator(c) (c == '+')
#define is_others(c) (c == '(' || c == ')')

using namespace std;

// Parse tree structure
struct ParseTree{
	string data; // Data stored
	int result = -1; // Result of subtree calculation
//	int diff = -1;	// Might be used for automatic differentiation, not used here
	struct ParseTree* left = nullptr;
	struct ParseTree* right = nullptr;
};

// Operator stack
stack<char> op_stack;
// Parse tree stack
stack<ParseTree*> parse_stack;
// Output queue
vector<string> o_vector;

// Convert character to integer
int char2int(char c){
	return c - '0';
}

// Initialize global variables
void initVariables() {
	while (!op_stack.empty()) {
		op_stack.pop();
	}
	while (!parse_stack.empty()) {
		parse_stack.pop();
	}
	o_vector.clear();
}

// + == - < * == / == % < ^
// 1    1   2    2    2
// Get the priority of an operator
int getPriority(char op1) {
	if (op1 == '(' || op1 == ')')
		return 0;
	if (op1 == '+' || op1 == '-')
		return 1;
	if (op1 == '*' || op1 == '/' || op1 == '%')
		return 2;
	if (op1 == '^')
		return 3;
	throw invalid_argument("Received invalid operator");
}

// Get the type of a character
enum CharType {Number, Function, Operator, Default, Others};
CharType getType(char c) {
	CharType type = Default;
	if ('0' <= c && c <= '9') {
		type = Number;
	}
	if (is_operator(c)) {
		type = Operator;
	}
	if (is_others(c)) {
		type = Others;
	}
	return type;
}

// Move the top of the operator stack to the output queue
void move2queue() {
	if (op_stack.empty()) {
		throw invalid_argument("Cannot pop an empty stack");
	}
	char top = op_stack.top();
	string temp(1, top);
	o_vector.push_back(temp);
	op_stack.pop();
}

// Push an accumulator number to the output queue
void push_accu(int accu) {
	if (accu < 0)
		return;
	string temp = to_string(accu);
	o_vector.push_back(temp);
}

// Shunting yard algorithm
bool shunting_yard(string input){
	int length = (int)input.length();
	// This flag is used to mark whether it is a continuous number, continuous numbers should be merged into one number.
	bool flagContinuousNumber = false;
	int accumulator = -1;
	
	// Begin Loop
	for (int i = 0; i < length; i++){
		CharType type = getType(input[i]);
		if (type == Default){
			flagContinuousNumber = false;
			push_accu(accumulator);
			accumulator = -1;
			continue;
		}
		if (type == Number) {
			if (flagContinuousNumber) { // last one is a number
				accumulator = accumulator * 10 + char2int(input[i]);
			} else { // last one is not a number, but this one is.
				flagContinuousNumber = true;
				accumulator = char2int(input[i]);
			}
			continue;
		} else {
			flagContinuousNumber = false;
			push_accu(accumulator);
			accumulator = -1;
		}
		if (type == Operator) {
			while(!op_stack.empty()) {
				if (getPriority(input[i]) <= getPriority(op_stack.top())) {
					move2queue();
				} else {
					break;
				}
			}
			op_stack.push(input[i]);
			continue;
		}
		if (type == Others) {
			if (input[i] == '(') {
				op_stack.push(input[i]);
			}
			if (input[i] == ')') {
				while (op_stack.top() != '(') {
					move2queue();
				}
				op_stack.pop();
			}
			continue;
		}
	}
	
	if (flagContinuousNumber)
		push_accu(accumulator);
	
	while (!op_stack.empty()) {
		char top = op_stack.top();
		if (top == '(' || top == ')') {
			return false;
		}
		string temp(1, top);
		o_vector.push_back(temp);
		op_stack.pop();
	}
	
	return true;
}


int main(){
	initVariables();
//	const string input = "(1+2) * (3 * (4+5))"; // 81
	const string input = "4+ 2 ^ 3 ^ 2 + 4 / 2"; // 516
	shunting_yard(input);
	return 0;
}