//
// FILE: postfixinfix.cpp
// Author: Leo Reyzin
// Purpose: RPN calculator that prints out infix expressions
// before evaluating them, using binary trees.
// HW3 of CS112B1 Spring 2003
// 
#include<iostream>
#include"stack2.h"
using namespace std;


struct TreeNode{
  // a tree node contains an operator if it has children
  // and a operand if it is a leaf
  // operator is misspelled on purpose, because otherwise it's a C++ keyword
  union {char operatr; float operand;};
  TreeNode *left, *right;

  TreeNode() {left=right=NULL;}
  TreeNode(float newoperand, TreeNode * newleft, TreeNode * newright) 
	{operand=newoperand; left=newleft; right=newright;}
  TreeNode(char newoperatr, TreeNode * newleft, TreeNode * newright) 
	{operatr=newoperatr; left=newleft; right=newright;}
};


// Prints the tree in infix notation,
// for example, ((5 / 2.5) - 1.5).
void InfixPrintTree (TreeNode * tree)
{
	FILL IN CODE HERE
}

// returns the value of the expression stored in a tree
// For example, for a tree storing ((5 / 2.5) - 1.5), it would return 0.5.
// For a NULL tree, or if the root is an unknown operator, returns 0.
float EvalTree (TreeNode * tree)
{
	FILL IN CODE HERE
}

// Deletes the entire tree (the root and the subtrees)
void DeleteTree(TreeNode * tree)
{
	FILL IN CODE HERE
}

int main()
{
  Stack s;
  char c;
  TreeNode * v1, * v2, * v3;
  float operand;
  bool done=false;

  // The loop below reads the input, one operator at a time,
  // and carries out the operation depending on the operator.
  // It stops upon receiving 'q' or if the read fails.
  while (!done) {

    if (!(cin >> c)) {
      cout << "Error: cannot read input\n";
      break;
    }

    switch (c) {
    case '?':
      if (!(cin >> operand)) { // Read the float input
        cout << "Error: cannot read float\n"; // cin failed to read the float
        done = true;                          // so we stop
      }

      // Create a new tree consisting
      // of a single node containing the operand,
      // and push its pointer on the stack
      else if ((v1=new TreeNode(operand, NULL, NULL))==NULL)
	cout<<"Out of Memory\n";
      else if (!s.Push(v1))
	  cout<<"Stack Overlow!\n";
      break;

    case '+':     // Handle all the arithmetic operators similarly
    case '-':
    case '*':
    case '/':
      FILL IN CODE HERE
      // It should pop two operands (handling stack underflow
	      // appropriately), create a new tree node with the
	      // operator and the two operands as children,
	      // and push the pointer to that treenode onto the stack

    case '=':     // Print the top of the stack by pop-print-push
      if(!s.Pop(v1)) {
        cout<<"Stack Empty!\n";
	break;
      }
      InfixPrintTree(v1);
      cout << " = ";
      cout << EvalTree(v1) << '\n';
      if(!s.Push(v1))
	  cout<<"Stack Overlow!\n";
     break;

    case 'p':     // Pop the top
      if(!s.Pop(v1))
        cout<<"Stack Empty!\n";
      DeleteTree(v1);
      break;

    case 'q':     // Quit
      done=true;
      break;

    default:
      cout<<"Invalid Entry!\n";
      break;
    }
  }

  // Empty the stack and delete all the trees
  while (s.Pop(v1))
    DeleteTree(v1);

  return 0;
}