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;

// 這裡定義的五種類型，分別是 數字，函數，操作符，默認，其他。
// 函數在這篇裡沒有實現，只實現了操作符。但結構都在這裡了，實現一個函數問題應該不大
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(“ received invalid operator “);
}

//得到字符所屬的類別
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(“ cannot pop a empty stack “);
	}
	char top = op_stack.top();
	string temp(1, top);
	o_vector.push_back(temp);
	op_stack.pop();
}

//將一個數字 push 到輸出隊列
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();
	// 這個 Flag 主要用來標記是否是連續的數字，連續的數字要合併為一個數字。
	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;
}