调度场算法/排程場演算法 和 逆波兰表示法
本帖最后由 傻眼貓咪 于 2022-5-8 10:24 编辑哈哈哈，每次都自己找自己麻烦{:10_291:}{:10_291:}{:10_291:}，找一些项目研究研究，头发快掉光了。本身是代码菜鸟，代码见笑了。
排程場演算法（或调度场算法）
Shunting Yard Algorithm
是一个用于将中缀表达式转换为字尾表达式的经典演算法，由艾兹格·迪杰斯特拉（Edsger Wybe Dijkstra）引入，因其操作类似于火车编组场而得名。
关于排程場演算法，网上应该容易找到其更为详细的基础原理解说，加上我解说能力有限，这里就不解说了{:10_245:} {:10_245:} {:10_245:}
逆波兰表示法
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 == '(') {
break;
}
else {
M = static_cast<int> (numbers.size());
calculate(numbers, numbers, OS);
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)) { // 如果是运算符 + - * /
M = static_cast<int> (numbers.size());
calculate(numbers, numbers, OS);
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)) { // 如果是运算符 + - * /
M = static_cast<int> (numbers.size());
calculate(numbers, numbers, OS);
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)) {
M = static_cast<int> (numbers.size());
calculate(numbers, numbers, OS);
numbers.pop_back();
}
else {
throw 505;
}
}
catch (...) {
cout << "异常处理：括号不匹配 或 运算子数量和数字不均！" << endl;
exit(0);
}
}
cout << numbers; // 利用逆波兰表达式求值法获得最终答案
return 0;
}5+((1+2)*4)-3
14
页:
[1]