调度场算法/排程場演算法 和 逆波兰表示法

傻眼貓咪

哈哈哈，每次都自己找自己麻烦，找一些项目研究研究，头发快掉光了。本身是代码菜鸟，代码见笑了。

排程場演算法（或调度场算法）
Shunting Yard Algorithm
是一个用于将中缀表达式转换为字尾表达式的经典演算法，由艾兹格·迪杰斯特拉（Edsger Wybe Dijkstra）引入，因其操作类似于火车编组场而得名。
关于排程場演算法，网上应该容易找到其更为详细的基础原理解说，加上我解说能力有限，这里就不解说了

逆波兰表示法
Reverse Polish notation
是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。逆波兰记法广泛地被用于计算器

举例： 中缀表示法 （3 + 4） 经过排程場演算法变成.. 后缀表示法（或逆波兰表示法）（3 4 + ）

---

一些题目中，表达式如：5+((1+2)*4)-3（有括号，有加减乘除符的优先级）想要用代码算出，并非一两行代码的事，网上很多大佬代码各式各样，但这里我就只用排程場演算法和逆波兰表示法计算出其结果吧，代码有点蔡，见笑了。

我的代码可以：
（一）加减乘除四个基本运算符的表达式运算
（二）有或无括号的表达式运算
（三）输入空格或无空格不影响结果，如：5      +(( 1+2)   *  4)   -3
（四）括号不匹配或数字量与运算子不均等异常处理，如：)5+2((
（五）数值只要计算过程在4字节（也就是 float 大小）范围内都可实现

C++

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cctype>
   
4. #include <cstdlib>
   
5. 
   
6. // 运算式
   
7. void calculate(float& a, float& b, char c) {
   
8.         switch (c)
   
9.         {
   
10.         case '+':
    
11.                 a += b;
    
12.                 break;
    
13.         case '-':
    
14.                 a -= b;
    
15.                 break;
    
16.         case '*':
    
17.                 a *= b;
    
18.                 break;
    
19.         case '/':
    
20.                 a /= b;
    
21.                 break;
    
22.         }
    
23. }
    
24. 
    
25. // 判断运算子
    
26. bool isSymbol(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }
    
27. 
    
28. using std::vector;
    
29. using std::cin, std::cout, std::endl;
    
30. int main(void) {
    
31.         
    
32.         vector <float> numbers; // 存储结果
    
33.         vector <char> OS; // operator stacking 运算子堆叠
    
34. 
    
35.         char c; // 用于测试输入字符
    
36.         float num; // 输入的数值
    
37.         int bracket = 0; // 左括号数量
    
38. 
    
39.         while ((c = cin.get()) != '\n') {
    
40. 
    
41.                 if (isdigit(c)) {
    
42.                         cin.unget();
    
43.                         cin >> num;
    
44.                         numbers.push_back(num);
    
45.                 }
    
46.                 else if (c == '(') {
    
47.                         OS.push_back(c);
    
48.                         bracket++;
    
49.                 }
    
50.                 else if (c == ')') {
    
51. 
    
52.                         // 异常处理，括号不匹配
    
53.                         try {
    
54.                                 bracket--;
    
55.                                 if (bracket < 0) {
    
56.                                         throw 505;
    
57.                                 }
    
58.                         }
    
59.                         catch (...) {
    
60.                                 cout << "异常处理：括号不匹配！" << endl;
    
61.                                 exit(0);
    
62.                         }
    
63.                         int N = static_cast<int> (OS.size()), M, n = 0;
    
64.                         for (int i = N - 1; i >= 0; i--) {
    
65.                                 n = i;
    
66.                                 if (OS[i] == '(') {
    
67.                                         break;
    
68.                                 }
    
69.                                 else {
    
70.                                         M = static_cast<int> (numbers.size());
    
71.                                         calculate(numbers[M - 2], numbers[M - 1], OS[i]);
    
72.                                         numbers.pop_back();
    
73.                                 }
    
74.                         }
    
75.                         OS.erase(OS.begin() + n, OS.end());
    
76.                 }
    
77.                 else if (c == '+' || c == '-') { // 运算子 + 或 -
    
78.                         int N = static_cast<int> (OS.size()), i = -1, M; // FILO 先进后出 first in last out
    
79.                         for (i = N - 1; i >= 0; i--) {
    
80.                                 if (isSymbol(OS[i])) { // 如果是运算符 + - * /
    
81.                                         M = static_cast<int> (numbers.size());
    
82.                                         calculate(numbers[M - 2], numbers[M - 1], OS[i]);
    
83.                                         numbers.pop_back();
    
84.                                 }
    
85.                                 else {
    
86.                                         break;
    
87.                                 }
    
88.                         }
    
89.                         if (i > 0) {
    
90.                                 OS.erase(OS.begin() + i, OS.end());
    
91.                         }
    
92.                         OS.push_back(c);
    
93.                 }
    
94.                 else if (c == '*' || c == '/') { // 运算子 * 或 /
    
95.                         int N = static_cast<int> (OS.size()), i = -1, M; // FILO 先进后出 first in last out
    
96.                         if (OS.back() == '*' || OS.back() == '/') {
    
97.                                 for (i = N - 1; i >= 0; i--) {
    
98.                                         if (isSymbol(OS[i])) { // 如果是运算符 + - * /
    
99.                                                 M = static_cast<int> (numbers.size());
    
100.                                                 calculate(numbers[M - 2], numbers[M - 1], OS[i]);
     
101.                                                 numbers.pop_back();
     
102.                                         }
     
103.                                         else {
     
104.                                                 break;
     
105.                                         }
     
106.                                 }
     
107.                         }
     
108.                         if (i > 0) {
     
109.                                 OS.erase(OS.begin() + i, OS.end());
     
110.                         }
     
111.                         OS.push_back(c);
     
112.                 }
     
113.         }
     
114. 
     
115.         for (int i = static_cast<int> (OS.size()) - 1, M; i >= 0; i--) {
     
116. 
     
117.                 // 异常处理：括号不匹配 或 运算子数量和数字不均
     
118.                 try {
     
119.                         if (numbers.size() > 1 && isSymbol(OS[i])) {
     
120.                                 M = static_cast<int> (numbers.size());
     
121.                                 calculate(numbers[M - 2], numbers[M - 1], OS[i]);
     
122.                                 numbers.pop_back();
     
123.                         }
     
124.                         else {
     
125.                                 throw 505;
     
126.                         }
     
127.                 }
     
128.                 catch (...) {
     
129.                         cout << "异常处理：括号不匹配 或 运算子数量和数字不均！" << endl;
     
130.                         exit(0);
     
131.                 }
     
132.         }
     
133. 
     
134.         cout << numbers[0]; // 利用逆波兰表达式求值法获得最终答案
     
135. 
     
136.         return 0;
     
137. }

复制代码

1. 5+((1+2)*4)-3
   
2. 14

复制代码