?
Nett. Ich hätte allerdings nicht die Operatoren selbst als Schlüssel benutzt, sondern aufsteigende Zahlen, über die ich die Operatorzeichen nachschlagen kann - dann lässt sich das hübsch in einer Schleife machen.
Es ist jetzt nicht so schön templatisiert und auch nicht rekursiv, dafür hab ich aber Funktionszeiger drin:
#include <cstddef>
#include <iostream>
#include <stack>
#include <vector>
double add (double x, double y) { return x + y; }
double subtract(double x, double y) { return x - y; }
double multiply(double x, double y) { return x * y; }
double divide (double x, double y) { return x / y; }
struct calculation {
char op_char;
unsigned priority;
double (*calc)(double, double);
} const calculations[] = {
{ '+', 0, add },
{ '-', 0, subtract },
{ '*', 1, multiply },
{ '/', 1, divide }
};
template<typename T, std::size_t N>
inline std::size_t array_size(T(&)[N]) { return N; }
bool next_combo(std::vector<std::size_t> &data) {
std::size_t max_value = array_size(calculations) - 1;
++data.back();
for(std::size_t i = data.size() - 1; i != 0 && data[i] > max_value; --i) {
data[i] = 0;
++data[i - 1];
}
return data[0] <= max_value;
}
void perform_top_operation(std::stack<double> &num_stack, std::stack<calculation> &op_stack) {
double x = num_stack.top(); num_stack.pop();
double y = num_stack.top(); num_stack.pop();
num_stack.push(op_stack.top().calc(y, x));
op_stack.pop();
}
int main() {
double numbers[] = { 1, 2, 3, 4 };
std::vector<std::size_t> op_indices(array_size(numbers) - 1, 0);
while(next_combo(op_indices)) {
// Was folgt, ist der relevante Teil des Shunting-Yard-Algorithmus
std::stack<calculation> op_stack;
std::stack<double> num_stack;
num_stack.push(numbers[0]);
for(std::size_t i = 0; i < op_indices.size(); ++i) {
calculation const ¤t_calc = calculations[op_indices[i]];
while(!op_stack.empty() && current_calc.priority <= op_stack.top().priority) {
perform_top_operation(num_stack, op_stack);
}
op_stack.push(current_calc);
num_stack.push(numbers[i + 1]);
}
while(!op_stack.empty()) {
perform_top_operation(num_stack, op_stack);
}
for(std::size_t i = 0; i < op_indices.size(); ++i) {
calculation const ¤t_calc = calculations[op_indices[i]];
std::cout << numbers[i] << ' ' << current_calc.op_char << ' ';
}
std::cout << numbers[op_indices.size()] << " = " << num_stack.top() << '\n';
}
}
