鱼C论坛

 找回密码
 立即注册
查看: 1762|回复: 0

[技术交流] 调度场算法/排程場演算法 和 逆波兰表示法

[复制链接]
发表于 2022-5-3 13:30:55 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 傻眼貓咪 于 2022-5-8 10:24 编辑

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

排程場演算法(或调度场算法)
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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-27 09:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表