// simple-expr-recognizer:
//   a recursive descent implementation of the grammar
//
// grammar:
//    Expression -> Term { '+' Term }*
//    Term       -> Factor { '*' Factor }*
//    Factor     -> Constant | '(' Expression ')'
//    Constant   -> [0-9]+
//
// Build:
//     g++ simple-expr-recognizer.cpp
//

#include <iostream>
#include <string>
using namespace std;

void parse_term();
void parse_factor();
void parse_constant();
char next_token();
void advance_to_next_token();
char next_token_type();
void fail(string msg);

void parse_expression() {
  parse_term();
  while ( next_token() == '+' ) {
    advance_to_next_token();
    parse_term();
  }
}

void parse_term() {
  parse_factor();
  while ( next_token() == '*' ) {
    advance_to_next_token();
    parse_factor();
  }
}

void parse_factor() {
  if ( next_token() == '(' ) {
    advance_to_next_token();
    parse_expression();       
    if ( next_token() != ')' )
       fail("expecting )");
    advance_to_next_token();
  } else {
    parse_constant();
  }
}

void parse_constant() {
  if ( next_token_type() != '0' )
     fail("expecting constant");
  advance_to_next_token();
}

void fail(string msg) {
  cout << "Input rejected: " << msg << endl;
  exit(1); // non-zero exit code indicates failure
}

string input;
int input_index = 0;

char next_token() {
  while ( input[input_index] == ' ' )
    ++input_index;
  return input[input_index];
}

void advance_to_next_token() {
  ++input_index;
}

char next_token_type() {
  char c = next_token();
  if ( isdigit( c  ) ) 
    return '0';
  else
    return '?';
}

int main() {
  cout << "Enter expression: ";
  getline(cin, input);
  input += "$";
  parse_expression();
  if ( next_token() != '$' ) {
    fail("expecting end of input");
  }
  cout << "Input accepted" << endl;
  return 0; // success
}