“调度场算法”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

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