// 
// Massingill, Berna L. and Oldham, Jeffrey D.
// 2000 Apr 5
// CS 1321
//
// Program to convert arithmetic expression in infix notation to 
//   equivalent expression in postfix (reverse Polish) notation.
//
// Input:  
//
//   A fully parenthesized arithmetic expression in infix notation,
//   with all terms (including variables, constants, operators,
//   *and parentheses*) separated by whitespace; terminated by
//   end-of-file.  
//
//   An expression is either:
//       "(" expression operator expression ")"
//     or
//       a single string (assumed to be a variable or constant)
//   An operator is any string.  
//
// Output:  
//
//   If the input expression is well-formed, an equivalent 
//   expression in postfix notation; otherwise an error message.
//

#include <iostream>
#include <stdlib.h>		// has exit(), EXIT_SUCCESS, EXIT_FAILURE
#include <string>
// ADD CODE HERE?
// DO NOT DISTRIBUTE
#include "tree.h"
#include "tree-debug.h"		// has printTree()

// Define shorthand for frequently-used types.
typedef Tree<string> expr_tree;
// end of DO NOT DISTRIBUTE

// ---- Function prototypes.  See below for comments. ----
void errorExit(void);
// ADD CODE HERE?
// DO NOT DISTRIBUTE
expr_tree infix2tree(istream & in);
void tree2postfix(const expr_tree & exprTree, ostream & out);
// end of DO NOT DISTRIBUTE

// ---- Main program. ----

int main(void)
{
  cout << "Enter the expression to evaluate "
    "(multiple lines okay, control-D to end):\n";

  // ADD CODE HERE
  // DO NOT DISTRIBUTE
  expr_tree eTree = infix2tree(cin);
  // If we didn't use all the input, expression is not well-formed.
  string temp;
  if (cin >> temp)
    errorExit();
  // Print expression tree (if DEBUG compile-time flag is set).
  printTree(cout, "\nExpression tree:\n", eTree);

  cout << "\nIn postfix notation:\n";
  tree2postfix(eTree, cout);
  cout << endl;
  // end of DO NOT DISTRIBUTE

  cout << "\nThat's all, folks!\n";
  return EXIT_SUCCESS;
}

// ---- Function definitions. ----
// YOU MAY FIND THESE FUNCTIONS USEFUL.

// Print error message and bail out of program. 
void errorExit(void)
{
  cerr << "Input expression is not well-formed.\n";
  exit(EXIT_FAILURE);
}

// ADD CODE HERE
// DO NOT DISTRIBUTE

// Read fully-parenthesized expression in infix notation from
//   input stream and convert to expression tree.  Exits with 
//   error message if input is not well-formed.
expr_tree infix2tree(istream & in)
{
  // Read first term, checking for end of input.
  string term;
  if (!(in >> term))
    errorExit();

  if (term == "(") {
    // Case 1:  expression begins with a parenthesis.
    expr_tree e1tree = infix2tree(in);
    string op;
    if (!(in >> op))
      errorExit();
    expr_tree e2tree = infix2tree(in);
    if (!(in >> term))
      errorExit();
    if (term != ")")
      errorExit();
    return expr_tree(op, e1tree, e2tree);
  }

  else {
  // Case 2:  expression must be a variable/constant.
    return expr_tree(term, expr_tree(), expr_tree());
  }
}
		     
// Print contents of expression tree in postfix notation to
//   output stream.
void tree2postfix(const expr_tree & eTree, ostream & out)
{
  if (!eTree.empty())
    {
      // Result is:
      //   operand 1
      tree2postfix(eTree.left(), out);
      //   followed by operand 2
      tree2postfix(eTree.right(), out);
      //   followed by operator
      out << eTree.item() << " ";
    }
  return;
}

// end of DO NOT DISTRIBUTE