// Programm: brackets.C
// Parser fuer Klammerausdruecke.
// Benutzt folgende kontextfreie Grammatik:
// parens_expr: '(' parens_expr ')' parens_expr
// epsilon
#include
#include
typedef std::string::const_iterator SSCI;
bool parens_expr(SSCI& b, SSCI e)
// PRE: [b,e) ist ein gueltiger range.
// POST: fuehrt die durch das Wort w in [b,e) eindeutig definierte
// Linksableitung durch. Der Rueckgabewert ist genau dann true, wenn
// die Ableitung gelingt; in diesem Fall ist [b,b') das abgeleitete
// Praefix von w, wobei b' der Wert der Variablen b am Ende der
// Funktion ist. Das Wort w ist genau dann ein gueltiger
// Klammerausdruck, wenn b' == e.
{
if (b == e || *b != '(')
return true; // epsilon ist das einzig ableitbare Praefix
// Klammerausdruck beginnt mit '(' und hat die Form (K1)K2
if (parens_expr(++b, e) && // leite K1 ab
b != e && *b == ')') // parse ')'
return parens_expr(++b, e); // leite K2 ab
return false; // K1 nicht ableitbar oder ')' fehlt
}
int main()
{
std::cout << "Eingabe eines Klammerausdrucks: ";
std::string input;
std::cin >> input;
SSCI beg = input.begin();
SSCI end = input.end();
if (parens_expr(beg, end) && beg == end)
std::cout << "Gueltiger";
else
std::cout << "Ungueltiger";
std::cout << " Klammerausdruck." << std::endl;
}
