stringstream: Wiederherstellung nach fehlgeschlagenden operator(>>)

[knivil]

Reicht es aus, sich mittels tellg die Position zu merken und nach fehlgeschlagem operator(>>) mittels seekg diese wieder herzustellen und clear aufzurufen? Ist noch etwas anderes zu beachten?

Beispiel: Ich parse einen mathematischen Ausdruck und erwarte entweder eine oeffnende Klammer '(', eine unaere Funktion wie tan, cos, ... oder eine Zahl:

struct token {
    type t; // <- e.g. Number, Bracket, Operation, Control
    union {
        double value; // <- e.g. 1.54, -134
        operation op; // <- e.g. '+', '-', '/'
        bracket brckt; // <- e.g. '{', '}', '(', ')'
        control cntrl; // <- FAIL error value
    };
};

// code
token t;
stringstream strm(input_string);
int pos = strm.tellg();

t.type = NUMBER;
strm >> t.value;
if (!strm.fail() && !strm.bad())
    return t;
// reset stringstream
strm.seekg(pos);
strm.clear();

// try to read bracket
// check and reset
// try to read unary function
// ...

[Werner Salomon]

.. schau Dir mal diesen mathematischen Parser an. Ich meld' mich spätestens morgen noch mal, wenn nötig.

[Sone]

strm >> t.value; 
if (!strm.fail() && !strm.bad()) 
    return t;

Das ist völlig bescheuert - erstens kann, wenn fail() false zurückgibt, bad() gar nicht true zurückgeben, und zweitens:
Wieso nicht das schönere Äquivalent?

if ( strm >> t.value ) 
    return t;

Zu deinem Problem: Der Stream bleibt nach Auftreten des Fehlers unbd clear() automatisch da zurück, wo er war, bevor der Fehler auftrat.
Siehe bspw.:

#include <iostream>
#include <sstream>
#include <iterator>

int main()
{
    std::istringstream stream("789 aaa");
    *std::istream_iterator<int>(stream);
    std::cout << stream.tellg() << '\n';

    *std::istream_iterator<int>(stream);
    stream.clear();
    std::cout << stream.tellg() << '\n';
}

Ausgabe: 3, 4.

[knivil]

Es ist nicht das, was ich suche, da gleich die Eingabe evaluiert wird. Das meochte ich nicht. Ich moechte eine Liste/std::vector von tokens haben. Diese werden dann von Infix nach Postfix umgewandelt und vielleicht mal evaluiert. Die Funktion ctest scheint etwa in die Richtung zu gehen, Leider arbeitet sie nur auf chars.

Da ich das Tokenizing von der Implementation vereinfachen wollte, moechte ich fuer jedes Token einen eigenen "Parser"/Funktion haben, der spekulativ auf den stringstream angesetzt wird. Das Ergebnis desjenigen, was keinen Fehler liefert, wird dann genommen. Das ist kein Problem, jedoch wollte ich operator(>>) nutzen, damit ich Zahlen nicht selber parsen muss. Bei Fehlschlag moechte ich aber den stringstream zuruecksetzen, so wie er vor dem Versuch war. Mir ist klar, dass das wahrscheinlich nicht fuer alle Streamklassen machbar ist, da einmal gelesene chars verloren sind. Aber vielleicht fuer stringstream. Wenn nicht, dann muss ich mir einen Adapter fuer Strings schreiben.

Das ist völlig bescheuert - erstens kann, wenn fail() false zurückgibt, bad() gar nicht true zurückgeben, und zweitens:

Whatever, ich wollte eof ausschliessen.

true if none of failbit or badbit is set. false otherwise.

Naja, also das gleiche.

Zu deinem Problem: Der Stream bleibt nach Auftreten des Fehlers unbd clear() automatisch da zurück, wo er war, bevor der Fehler auftrat.

Gibt es das irgendwo schwarz auf weiss?

std::istringstream stream("78.3ee9 aaa"); 
std::cerr << *std::istream_iterator<double>(stream) << '\n'; 
stream.clear(); 
std::cout << stream.tellg() << '\n';

It does not work.

[Sone]

knivil schrieb:

Zu deinem Problem: Der Stream bleibt nach Auftreten des Fehlers unbd clear() automatisch da zurück, wo er war, bevor der Fehler auftrat.

Gibt es das irgendwo schwarz auf weiss?

Hmm. Das ist das Problem - ich bin mir sicher, dass wird irgendwie im Standard impliziert. Also dass die interne Position des Streambuffers nicht verändert wird, solange nicht erfolgreich gelesen wurde o.ä.

Aber wenn das tatsächlich nirgends steht... dann musst du wohl tatsächlich auch Nummer sicher gehen.

[Sone]

knivil schrieb:

std::istringstream stream("78.3ee9 aaa"); 
std::cerr << *std::istream_iterator<double>(stream) << '\n'; 
stream.clear(); 
std::cout << stream.tellg() << '\n';

It does not work.

Er sollte das doch richtig lesen....! Da ist eine gültige Fließkommazahl - 78.9!
Obwohl er wahrscheinlich bei "ee9" den Fehler findet. Dann ist meine Aussage aber immer noch richtig: Da wo der Fehler auftritt, direkt wo der Exponent sein sollte ist ein 'e'.

[hustbaer]

knivil schrieb:

Zu deinem Problem: Der Stream bleibt nach Auftreten des Fehlers unbd clear() automatisch da zurück, wo er war, bevor der Fehler auftrat.

Gibt es das irgendwo schwarz auf weiss?

Nein, weil's ja auch nicht stimmt. Behaupte ich mal. Zumindest hätte ich darüber auch nichts gefunden. Die Definition der Extraction-Operatoren liest sich für mich nicht danach als ob es so eine Garantie/Forderung gäbe.
(Und sie wäre auch nicht überall umsetzbar, von daher...)

Es funktioniert nur, wenn 1) keine Whitespaces übersprungen wurden und 2) der Extraction-Operator noch nix konsumiert hat.

D.h. falls Whitespaces vernichtet wurden kommen die sowieso nicht wieder. Niemals.

Und die meisten vordefinierten Extraction-Operatoren sind "passend" definiert, so dass sie entweder

1. wissen dass sie fehlschlagen werden bevor das erste Zeichen konsumiert wurde
   oder
2. erfolgreich durchlaufen können.

Zumindest wenn man Kleinigkeiten wie Overflows o.ä. ignoriert (ich weiss nicht wie die Extraction-Operatoren mit sowas umgehen).

Und ich schreibe "die meisten", weil ich z.B. nicht wüsste wie es für bool im boolalpha Mode gehen sollte, wenn man versucht sowas wie "faxen" oder "trullala" als bool zu extrahieren.

[hustbaer]

Sone schrieb:

Dann ist meine Aussage aber immer noch richtig: Da wo der Fehler auftritt, direkt wo der Exponent sein sollte ist ein 'e'.

Dann war deine Aussage ...

1. Nicht klar. Ich hab das z.B. auch anders verstanden. "Da wo er war, bevor der Fehler auftrat" heisst für mich "wenn Fehler, dann Stream danach unverändert, als ob ich nicht probiert hätte was zu lesen".
2. Sinnfrei. Weil es hier ja gerade darum geht ein "undo" auf den Stream zu machen.

[Sone]

hustbaer schrieb:

knivil schrieb:

Zu deinem Problem: Der Stream bleibt nach Auftreten des Fehlers unbd clear() automatisch da zurück, wo er war, bevor der Fehler auftrat.

Gibt es das irgendwo schwarz auf weiss?

Nein, weil's ja auch nicht stimmt. Behaupte ich mal. Zumindest hätte ich darüber auch nichts gefunden. Die Definition der Extraction-Operatoren liest sich für mich nicht danach als ob es so eine Garantie/Forderung gäbe.

Falsch bis zum Beweis der Richtigkeit. So ist es.

wissen dass sie fehlschlagen werden bevor das erste Zeichen konsumiert wurde

Wie soll das gehen? Wenn du den String "aa" hast, wie kann dein istream::operator>>(int&) wissen, dass die Extraktion fehlschlägt, bevor er anfängt zu lesen?
(Ich glaube, ich hab was missverstanden)

[hustbaer]

knivil schrieb:

Beispiel: Ich parse einen mathematischen Ausdruck und erwarte entweder eine oeffnende Klammer '(', eine unaere Funktion wie tan, cos, ... oder eine Zahl:

Das würde sich ja noch einfach mit is >> ws gefolgt von is.peek() erschlagen lassen.

[Sone]

hustbaer schrieb:

knivil schrieb:

Beispiel: Ich parse einen mathematischen Ausdruck und erwarte entweder eine oeffnende Klammer '(', eine unaere Funktion wie tan, cos, ... oder eine Zahl:

Das würde sich ja noch einfach mit is >> ws gefolgt von is.peek() erschlagen lassen.

Ahh, du meinst peek()? Das verstehe ich aber als Lesen des ersten Zeichens. Zwar wird die Position im Streambuffer nicht erhöht, aber das erste Zeichen hamse ja.

[hustbaer]

Sone, ich hab konsumiert geschrieben, nicht untersucht.
Und ja, ich meine peek.

Weil der istream_iterator über den das alles definiert ist halt in operator * nur peekt, so lange man operator ++ nicht aufruft.
Mach deinen Standard auf und guck nach wenns dich interessiert.

EDIT: Er. istreambuf_iterator vermutlich, nicht istream_iterator . Müsste selbst nochmal nachsehen. Irgend ein scheiss Iterator auf jeden Fall.

[Werner Salomon]

Hallo knivil,

ich halte es grundsätzlich für eine schlechte Idee, einen Stream auf Verdacht in den fail-Zustand zu schicken und dann eine alternatives Lesen zu versuchen.
Aus zwei Gründen:
1. zum einen kann der Anwender von außen mit der Methode exceptions dafür sorgen, dass das Setzendes failbits zu einer Exception führt.
2. zum anderen ist es zwar korrekt, dass nach Setzen des failbits nicht weiter gelesen wird, aber das failbit wird erst gesetzt, wenn ein Fehler erkannt wurde, und dies muss nicht mit dem ersten Zeichen geschehen. Du weißt also nicht wirklich wo der Lesezeiger nach fail wirklich steht.

Wenn Die Alternativen "Number, Bracket und Operation" sind, so ist es doch ein leichtes zuerst auf "Bracket und Operation" abzufragen und erst wenn das nicht passt zu entscheiden ob der Ausdruck beendet ist, oder ob eine Nummer folgen muss(!).
Die Herausforderung besteht also darin, dass nächste Zeichen zu interpretieren ohne es ggf. zu konsumieren. Das geht im Prinzip auf zwei Arten:
1. Du liest zunächst genau ein Zeichen, prüfst es ob es ein Operator ist, bzw. eine Klammer, und falls nicht, stellst Du es mit putback wieder zurück.
2. Du prüfst das nächste Zeichen mit peek.
In beiden Fällen, muss man sehr sorgfältig mit dem EOF-Flag und dem optionalen Überlesen von Whitespace-Charactern umgehen. Aus diesem Grund habe ich das Helferlein ctest geschrieben, was das Handling vereinfacht. Es geht aber auch ohne - hier mal eine Skizze, die Whitespace-Character innerhalb des mathematischen Ausdruck zulässt:

#include <iostream>

struct AusdruckLeser
{
    AusdruckLeser( int& wert )
        : wert_( wert )
    {}
    int& wert_;
};
std::istream& operator>>( std::istream& in, AusdruckLeser a );

struct FaktorLeser
{
    FaktorLeser( int& wert )
        : wert_( wert )
    {}
    int& wert_;
};

std::istream& operator>>( std::istream& in, FaktorLeser f )
{
    char c;
    in >> c;
    if( c == '(' )
    {
        if( in >> AusdruckLeser( f.wert_ ) >> c && c != ')' )
            in.setstate( std::ios_base::failbit );
    }
    else
        in.putback( c ) >> f.wert_;
    return in;
}

std::istream& operator>>( std::istream& in, AusdruckLeser a )
{
    in >> FaktorLeser( a.wert_ );
    while( in.good() && !(in >> std::ws).eof() )
    {
        char op; // ggf. Operator lesen
        if( in >> op )
        {
            int param2;
            switch( op )
            {
            case '+':
                if( in >> FaktorLeser( param2 ) )
                    a.wert_ += param2;
                break;
            case '-':
                if( in >> FaktorLeser( param2 ) )
                    a.wert_ -= param2;
                break;
            default:
                return in.putback( op );
            }
        }
    }
    return in;
}

int main()
{
    using namespace std;
    for( int i; cin >> AusdruckLeser( i ); cin.ignore(1) )
        cout << "Ergebnis: " << i << endl;
}

Das letzte ignore(1) überspringt das Zeichen, das den Ausdruck begrenzt. Der Dialog könnte z.B. so aussehen:

7- (3 - 5);
Ergebnis: 9
1+2+3+4 + 5;
Ergebnis: 15
17-(25-(3+5+1));
Ergebnis: 1

Gruß
Werner

[iobash]

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.