001
26.11.2008, 18:45 Uhr
0xdeadbeef
Gott
(Operator)
|
Ich hab da noch etwas alten Code in der Richtung rumliegen:
| C++: |
#include <cmath>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
struct token {
enum id_t {
op_id,
num_id
};
union {
char op;
double x;
} val;
id_t type;
};
std::string const ops = "+-*/^()";
std::istream &get_token(std::istream &in, token &tok) {
double x;
char c;
if(in >> c) {
if(ops.find(c) == std::string::npos) {
in.unget();
in >> x;
tok.val.x = x;
tok.type = token::num_id;
} else {
tok.val.op = c;
tok.type = token::op_id;
}
}
return in;
}
double eval(double x, double y, char op) {
switch(op) {
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '/': return x / y;
case '^': return std::pow(x, y);
}
throw std::runtime_error(std::string(1, op));
}
double solve(std::string equation) {
std::stack<double> num_stack;
std::stack<char> op_stack;
std::map<char, int> pcd_map;
pcd_map['('] = -1;
pcd_map['+'] = pcd_map['-'] = 0;
pcd_map['*'] = pcd_map['/'] = 1;
pcd_map['^'] = 3;
std::istringstream is;
token tok;
is.str(equation);
while(get_token(is, tok)) {
switch(tok.type) {
case token::num_id:
{
num_stack.push(tok.val.x);
break;
}
case token::op_id:
{
char op1 = tok.val.op;
if(op1 == '(') {
op_stack.push('(');
} else if(op1 == ')') {
char op2;
while((op2 = op_stack.top()) != '(') {
double x, y;
op_stack.pop();
x = num_stack.top(); num_stack.pop();
y = num_stack.top(); num_stack.pop();
num_stack.push(eval(y, x, op2));
}
op_stack.pop();
} else {
char op2;
while(op1 != '^' && // rechtsassoziativ, derzeit hoechste Prioritaet
op_stack.size() > 0 &&
ops.find(op2 = op_stack.top()) != std::string::npos &&
pcd_map[op1] <= pcd_map[op2]) {
double x, y;
op_stack.pop();
x = num_stack.top(); num_stack.pop();
y = num_stack.top(); num_stack.pop();
num_stack.push(eval(y, x, op2));
}
op_stack.push(op1);
}
break;
}
}
}
while(op_stack.size() > 0) {
char op = op_stack.top();
double x, y;
op_stack.pop();
x = num_stack.top(); num_stack.pop();
y = num_stack.top(); num_stack.pop();
num_stack.push(eval(y, x, op));
}
return num_stack.top();
}
int main() {
std::string equation;
std::getline(std::cin, equation);
std::cout << solve(equation) << std::endl;
}
|
Nicht direkt golfig, hat dafür aber auch keine Probleme mit (3 + 4) * 5^2. 
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra |
