?
Ich hab mal in meiner Kiste gekramt und das hier rausgezogen:
token.hh
#ifndef INCLUDED_TOKEN_HH
#define INCLUDED_TOKEN_HH
#include <istream>
struct token {
enum id_t {
op_id,
num_id,
var_id
};
union {
char op;
double x;
} val;
id_t type;
};
std::istream &operator>>(std::istream &in, token &tok);
#endif
token.cc
#include "token.hh"
#include "op_map.hh"
#include <cctype>
std::istream &operator>>(std::istream &in, token &tok) {
char c;
if(in >> c) {
if(std::tolower(c) == 'x') {
tok.type = token::var_id;
} else if(std::isdigit(c)) {
in.unget();
double x;
if(in >> x) {
tok.val.x = x;
tok.type = token::num_id;
}
} else if(op_map::instance().is_valid(c)) {
tok.val.op = c;
tok.type = token::op_id;
} else {
in.setstate(in.rdstate() | std::istream::failbit);
}
}
return in;
}
op_map.hh
#ifndef INCLUDED_OP_MAP_HH
#define INCLUDED_OP_MAP_HH
#include <map>
#include <utility>
typedef double(*eval_func_t)(double, double);
typedef std::pair<int, eval_func_t> op_record_t;
class op_map {
public:
op_map();
bool is_valid(char c) const;
int priority(char c) const;
eval_func_t function(char c) const;
static op_map const &instance();
private:
std::map<char, op_record_t> data_;
};
#endif
op_map.cc
#include "op_map.hh"
#include <cmath>
#include <stdexcept>
template<char op> double eval_func(double, double) { throw std::invalid_argument("Ungültiger Operator"); }
template<> double eval_func<'+'>(double x, double y) { return x + y; }
template<> double eval_func<'-'>(double x, double y) { return x - y; }
template<> double eval_func<'*'>(double x, double y) { return x * y; }
template<> double eval_func<'/'>(double x, double y) { return x / y; }
template<> double eval_func<'^'>(double x, double y) { return std::pow(x, y); }
op_map::op_map() {
data_['('] = op_record_t(-1, eval_func<'('>);
data_[')'] = op_record_t(-1, eval_func<')'>);
data_['+'] = op_record_t( 0, eval_func<'+'>);
data_['-'] = op_record_t( 0, eval_func<'-'>);
data_['*'] = op_record_t( 1, eval_func<'*'>);
data_['/'] = op_record_t( 1, eval_func<'/'>);
data_['^'] = op_record_t( 2, eval_func<'^'>);
}
bool op_map::is_valid(char c) const { return data_.find(c) != data_.end(); }
int op_map::priority(char c) const { return data_.find(c)->second.first ; }
eval_func_t op_map::function(char c) const { return data_.find(c)->second.second; }
op_map const &op_map::instance() {
static const op_map me;
return me;
}
read_type.hh
#ifndef INCLUDED_READ_TYPE_HH
#define INCLUDED_READ_TYPE_HH
#include <iostream>
#include <sstream>
#include <string>
template<typename result_t>
result_t read_type_ref(result_t &dest,
std::string const &prompt,
std::istream &in = std::cin,
std::ostream &out = std::cout) {
std::istringstream parser;
std::string line;
do {
parser.clear();
out << prompt << std::flush;
std::getline(in, line);
parser.str(line);
parser >> dest;
} while(!parser);
return dest;
}
template<typename result_t>
result_t read_type(std::string const &prompt,
std::istream &in = std::cin,
std::ostream &out = std::cout) {
result_t result;
return read_type_ref(result, prompt, in, out);
}
#endif
calc.cc
#include "op_map.hh"
#include "read_type.hh"
#include "token.hh"
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
template<typename T> T top_and_pop(std::stack<T> &s) {
T ret = s.top();
s.pop();
return ret;
}
void perform_top_operation(std::stack<double> &num_stack,
std::stack<char> & op_stack) {
if(num_stack.size() < 2 || op_stack.empty()) {
throw std::invalid_argument("Ungültiger Ausdruck");
}
char op;
double x, y;
op = top_and_pop(op_stack);
x = top_and_pop(num_stack);
y = top_and_pop(num_stack);
num_stack.push(op_map::instance().function(op)(y, x));
}
double solve(std::string equation, double var_x) {
std::stack<double> num_stack;
std::stack<char > op_stack;
std::istringstream is(equation);
token tok;
while(is >> tok) {
switch(tok.type) {
case token::var_id:
{
num_stack.push(var_x);
break;
}
case token::num_id:
{
num_stack.push(tok.val.x);
break;
}
case token::op_id:
{
char op = tok.val.op;
if(op == '(') {
op_stack.push(op);
} else if(op == ')') {
// Lazy-Evaluation, damit op_stack.top() nicht bei leerem Stack
// ausgeführt wird. Das funktioniert, weil perform_top_operation bei
// leerem op_stack eine Exception schmeißt.
while(op_stack.empty() || op_stack.top() != '(') {
perform_top_operation(num_stack, op_stack);
}
op_stack.pop();
} else {
while(op != '^' && // rechtsassoziativ, derzeit hoechste Priorität
!op_stack.empty() &&
op_map::instance().priority(op) <= op_map::instance().priority(op_stack.top())) {
perform_top_operation(num_stack, op_stack);
}
op_stack.push(op);
}
break;
}
}
}
// num_stack.empty() ist nur true, wenn ein leerer
// Ausdruck bzw. (), (()) etc. angegeben wurde -
// perform_top_operation schmeißt dann einen Fehler (s.o.)
while(!op_stack.empty() || num_stack.empty()) {
perform_top_operation(num_stack, op_stack);
}
return num_stack.top();
}
int main() {
std::string equation;
while(std::getline(std::cin, equation)) {
if(equation == "quit" ||
equation == "exit") {
break;
}
double x = read_type<double>("x = ");
try {
std::cout << std::setprecision(15) << solve(equation, x) << std::endl;
} catch(std::invalid_argument &e) {
std::cerr << e.what() << std::endl;
}
}
}
Makefile
#!/usr/bin/make
TARGET = calc
CXX = g++
CXXFLAGS = -Wall -Wextra -pedantic -O2
LIBS =
SRCS = $(wildcard *.cc)
OBJS = $(SRCS:%.cc=%.o)
DEPFILE = .depend
all: dep $(TARGET)
dep: $(DEPFILE)
$(DEPFILE): $(SRCS)
$(CXX) -MM $+ > $@
-include $(DEPFILE)
$(TARGET): $(OBJS)
$(CXX) $(CXXFLAGS) $(LIBS) $+ -o $@
clean:
rm $(OBJS)
distclean: clean
rm $(TARGET)
rm $(DEPFILE)
.PHONY: all dep clean distclean
Das ganze implementiert den Shunting-Yard-Algorithmus derart, dass beim Umstellen des Ausdrucks gleichzeitig ausgewertet wird. Wenn der selbe Ausdruck oft mit verschiedenen x ausgewertet werden soll, ist das natürlich nicht der performanteste Ansatz, und es gibt ein paar kleinere Unschönheiten in der Implementierung (die Sonderbehandlung für ^ beispielsweise), aber in der Art könnte man das machen, ohne gleich große Kanonen auszupacken.
