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;

// 解析木構造体
struct ParseTree{
	string data; // 保存するデータ
	int result = -1; // サブツリー計算の結果
//	int diff = -1;	// 自動微分で使用する可能性があるが、ここでは使用しない
	struct ParseTree* left = nullptr;
	struct ParseTree* right = nullptr;
};

// 演算子スタック
stack<char> op_stack;
// 解析木配列
stack<ParseTree*> parse_stack;
// 出力キュー
vector<string> o_vector;

// ここで定義された5種類のタイプは、それぞれ数字、関数、演算子、デフォルト、その他です。
// この文では関数は実装されていませんが、演算子は実装されています。構造はここにあるので、関数を実装するのは問題ないでしょう。
enum CharType {Number, Function, Operator, Default, Others};

// 文字を数字に変換
int char2int(char c){
	return c - ‘0’;
}

//グローバル変数の初期化
void initVariables() {
	while (!op_stack.empty()) {
		op_stack.pop();
	}
	while (!parse_stack.empty()) {
		parse_stack.pop();
	}
	o_vector.clear();
}

// + == - < * == / == % < ^
// 1    1   2    2    2
// 演算子の優先度を取得
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(“ 無効な演算子を受け取りました “);
}

//文字のタイプを取得
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;
}

//演算子スタックのトップを出力キューに移動
void move2queue() {
	if (op_stack.empty()) {
		throw invalid_argument(“ 空のスタックからポップできません “);
	}
	char top = op_stack.top();
	string temp(1, top);
	o_vector.push_back(temp);
	op_stack.pop();
}

//数字を出力キューにプッシュ
void push_accu(int accu) {
	if (accu < 0)
		return;
	string temp = to_string(accu);
	o_vector.push_back(temp);
}

//調度場の主要アルゴリズム
bool shunting_yard(string input){
	int length = (int)input.length();
	// このフラグは連続した数字を示すためのもので、連続した数字は1つの数字に統合されます。
	bool flagContinuousNumber = false;
	int accumulator = -1;
	
	// ループ開始
	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) { // 最後のものは数字
				accumulator = accumulator * 10 + char2int(input[i]);
			} else { // 最後のものは数字でなく、これは数字です。
				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;
}