?
Werner Salomon schrieb:
In beiden Fällen, muss man sehr sorgfältig mit dem EOF-Flag und dem optionalen Überlesen von Whitespace-Charactern umgehen.
Mit den IOStreams muss man immer sehr sehr sorgfältig umgehen, das ist bekannt. Dass sie etwas Overhead haben und dadurch langsam sind auch (gilt insbesondere stringstreams).
Ebenso dass sie nur mit LL(1)-Grammatiken umgehen können und Schwierigkeiten haben, zwischen verschiedenen Eingabeformaten zu wechseln.
Als Beispiel ist es relativ schwer, deinem Parser zu sagen, dass er zwar Whitespaces ignorieren, aber am Zeilenende stoppen soll. Wenn irgendwann Ganzzahlen und Fliesskommazahlen unterschiedlich behandelt werden sollen (bspw. um Brüche zu unterstützen) wird das ein rechtes Gefrickel. Dann bin ich mit const char* besser dran, weil ich da ganz ein RAII-Objekt zum Backtracken benutzen kann (BacktrackGuard, das scheint für C-Strings das zu sein, was knivil für Streams sucht). Backtracking und Streams vertragen sich nicht. Den Streambuf dazu vergewaltigen möchte auch niemand.
Hier eine Alternative zu deinem mathematischen Parser in weniger Zeilen und mehr Funktinoalität:
#include <iostream>
#include <functional>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <string>
typedef double value_type;
typedef std::function<value_type(value_type, value_type)> binary_operator;
struct operator_info {
int precedence;
bool right_associative;
binary_operator apply;
int effective_precedence() const { return precedence + right_associative; }
};
std::unordered_map<char, operator_info> operators {
{'\0',{0, false, std::plus<value_type>()}},
{')', {0, false, std::plus<value_type>()}},
{'+', {1, false, std::plus<value_type>()}},
{'-', {1, false, std::minus<value_type>()}},
{'*', {2, false, std::multiplies<value_type>()}},
{'/', {2, false, std::divides<value_type>()}},
{'^', {3, true, (value_type(*)(value_type,value_type))std::pow}},
};
std::unordered_map<std::string, std::function<value_type(value_type)> > functions {
{"sin", (value_type(*)(value_type))std::sin},
{"cos", (value_type(*)(value_type))std::cos},
{u8"√", (value_type(*)(value_type))std::sqrt}, // Hier macht das Forum etwas
{u8"∛", [](value_type v){return std::pow(v, 1/3.);}}, // verquert, das soll das
{u8"∜", [](value_type v){return std::pow(v, 1/4.);}}, // Unicode-Wurzelzeichen sein.
};
const char * ignore_spaces(const char *& p)
{
while (std::isspace(*p)) ++p;
return p;
}
const char *error_happened = "";
value_type parse_value(const char *& p, const char *& errmsg)
{
static_assert(std::is_same<value_type,double>::value, "change strtod");
char *end; // because strtod is not const-correct
value_type val = strtod(p, &end);
p = p != end ? end : (errmsg = "not a double", error_happened);
return val;
}
std::string parse_identifier(const char *& p, const char *&)
{
const char *start = p;
for (;*p&&*p!='('&&!std::isspace(*p)&&!std::isdigit(*p)&&!operators.count(*p);++p) {}
return std::string(start, p - start);
}
double parse(const char *& p, const char *& errmsg)
{
if (!*p) { p = error_happened, errmsg = "expression expected"; return 0; }
std::stack<std::pair<int, binary_operator> > ops;
std::stack<value_type> stack;
ops.push({-1, {}}); // sentinel
for (; *p; ++p) {
if (*ignore_spaces(p) != '(') {
const char *p_old = p; // !! nur als Beispiel für Backtracking, hier nicht nötig
stack.push(parse_value(p, errmsg));
if (p == error_happened) {
p = p_old; // !! nur als Beispiel für Backtracking, hier nicht nötig
auto f = functions.find(parse_identifier(p, errmsg));
if (f == functions.end()) p = error_happened, errmsg = "not a function";
else stack.top() = f->second(parse(p, errmsg));
}
} else {
stack.push(parse(++p, errmsg));
if (*p == ')') ++p;
else if (p != error_happened) p = error_happened, errmsg = "missing )";
}
auto op = operators.find(*ignore_spaces(p));
if (op == operators.end()) {
p = error_happened, errmsg = "not an operator";
break;
}
for (; ops.top().first >= op->second.effective_precedence(); ops.pop()) {
auto top = stack.top(); stack.pop();
stack.top() = ops.top().second(stack.top(), top);
}
if (*p == ')' || !*p)
break;
ops.emplace(op->second.precedence, op->second.apply);
}
if (ops.size() > 1) p = error_happened, errmsg = "too many operators";
return stack.top();
}
struct parse_full {
const char *c;
parse_full(const char *c) : c(c) {}
};
std::ostream& operator<<(std::ostream& os, parse_full const& p)
{
const char *c = p.c, *errmsg="unset";
value_type result = parse(c, errmsg);
if (c == error_happened) return os << " syntax error: " << errmsg;
else if (*c == ')') return os << " syntax error: missing (";
else return os << " = " << result;
}
int main()
{
for (std::string s; std::cout << "> ", std::getline(std::cin, s);)
std::cout << parse_full(s.c_str()) << '\n';
}
> 4.78*3.22+5-4.99/4.3
4.78*3.22+5-4.99/4.3
= 19.2311
> 6.6-(3+1.2*2)
6.6-(3+1.2*2)
= 1.2
> 17-(25-(3+5+1))
17-(25-(3+5+1))
= 1
> 8/2/2
8/2/2
= 2
> 2^2^2^2
2^2^2^2
= 65536
> sin(√2)
= 0.987766
>
syntax error: expression expected
> (1
(1
syntax error: missing )
> 1+
1+
syntax error: too many operators
> 1)
1)
syntax error: missing (
Die Eingabe in Zeile 16 ist "sin(√2)", das Forum scheint Unicode in Codeblöcken zu htmlescapen. Das ist ein weiterer Vorteil dieses Ansatzes: Dank UTF-8 ist er unicode-aware.
Für etwas komplexere Grammatiken lässt sich recht einfach ein Tokenizer auf const char* aufbauen. Das schöne ist halt, dass C-Strings nullterminiert sind. Gute Parser machen davon Gebrauch und müssen fast nie auf End-Of-String testen, weil *p == wert kann nur sein, wenn *p != '\0' . Ein Istream muss immer auf Validität geprüft werden, bei C-Strings ist das nicht nötig. Das reduziert Code, Fehleranfälligkeit und Performance.
