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

傻眼貓咪

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

排程場演算法（或调度场算法）
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++

#include <iostream>
#include <vector>
#include <cctype>
#include <cstdlib>

// 运算式
void calculate(float& a, float& b, char c) {
        switch (c)
        {
        case '+':
                a += b;
                break;
        case '-':
                a -= b;
                break;
        case '*':
                a *= b;
                break;
        case '/':
                a /= b;
                break;
        }
}

// 判断运算子
bool isSymbol(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

using std::vector;
using std::cin, std::cout, std::endl;
int main(void) {
        
        vector <float> numbers; // 存储结果
        vector <char> OS; // operator stacking 运算子堆叠

        char c; // 用于测试输入字符
        float num; // 输入的数值
        int bracket = 0; // 左括号数量

        while ((c = cin.get()) != '\n') {

                if (isdigit(c)) {
                        cin.unget();
                        cin >> num;
                        numbers.push_back(num);
                }
                else if (c == '(') {
                        OS.push_back(c);
                        bracket++;
                }
                else if (c == ')') {

                        // 异常处理，括号不匹配
                        try {
                                bracket--;
                                if (bracket < 0) {
                                        throw 505;
                                }
                        }
                        catch (...) {
                                cout << "异常处理：括号不匹配！" << endl;
                                exit(0);
                        }
                        int N = static_cast<int> (OS.size()), M, n = 0;
                        for (int i = N - 1; i >= 0; i--) {
                                n = i;
                                if (OS[i] == '(') {
                                        break;
                                }
                                else {
                                        M = static_cast<int> (numbers.size());
                                        calculate(numbers[M - 2], numbers[M - 1], OS[i]);
                                        numbers.pop_back();
                                }
                        }
                        OS.erase(OS.begin() + n, OS.end());
                }
                else if (c == '+' || c == '-') { // 运算子 + 或 -
                        int N = static_cast<int> (OS.size()), i = -1, M; // FILO 先进后出 first in last out
                        for (i = N - 1; i >= 0; i--) {
                                if (isSymbol(OS[i])) { // 如果是运算符 + - * /
                                        M = static_cast<int> (numbers.size());
                                        calculate(numbers[M - 2], numbers[M - 1], OS[i]);
                                        numbers.pop_back();
                                }
                                else {
                                        break;
                                }
                        }
                        if (i > 0) {
                                OS.erase(OS.begin() + i, OS.end());
                        }
                        OS.push_back(c);
                }
                else if (c == '*' || c == '/') { // 运算子 * 或 /
                        int N = static_cast<int> (OS.size()), i = -1, M; // FILO 先进后出 first in last out
                        if (OS.back() == '*' || OS.back() == '/') {
                                for (i = N - 1; i >= 0; i--) {
                                        if (isSymbol(OS[i])) { // 如果是运算符 + - * /
                                                M = static_cast<int> (numbers.size());
                                                calculate(numbers[M - 2], numbers[M - 1], OS[i]);
                                                numbers.pop_back();
                                        }
                                        else {
                                                break;
                                        }
                                }
                        }
                        if (i > 0) {
                                OS.erase(OS.begin() + i, OS.end());
                        }
                        OS.push_back(c);
                }
        }

        for (int i = static_cast<int> (OS.size()) - 1, M; i >= 0; i--) {

                // 异常处理：括号不匹配 或 运算子数量和数字不均
                try {
                        if (numbers.size() > 1 && isSymbol(OS[i])) {
                                M = static_cast<int> (numbers.size());
                                calculate(numbers[M - 2], numbers[M - 1], OS[i]);
                                numbers.pop_back();
                        }
                        else {
                                throw 505;
                        }
                }
                catch (...) {
                        cout << "异常处理：括号不匹配 或 运算子数量和数字不均！" << endl;
                        exit(0);
                }
        }

        cout << numbers[0]; // 利用逆波兰表达式求值法获得最终答案

        return 0;
}

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