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;
}