//
// 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)
{
  if (tree!=NULL) {
    // If it's a leaf, it has an operand, which should be printed
    // by itself without parens
    if (tree->left==NULL && tree->right==NULL)
      cout<<tree->operand;

    // else print parent, left subtree, operatr, right subtree, paren
    else {
      cout<<'(';
      InfixPrintTree(tree->left);
      cout<<' ';
      cout<<tree->operatr;
      cout<<' ';
      InfixPrintTree(tree->right);
      cout<<')'; 
   }
  }
}

// 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)
{
  if (tree==NULL)
    return 0;

  // If it's a leaf, it contains an operand, which is the value
  // we need to return
  if (tree->left==NULL && tree->right==NULL)
    return tree->operand;

  // else evaluate the two subtrees and the perform the operation on them
  else {
    float v1=EvalTree(tree->left);
    float v2=EvalTree(tree->right);
    switch (tree->operatr) {
    case '+':
      return v1+v2;
    case '-':
      return v1-v2;
    case '*':
      return v1*v2;
    case '/':
      return v1/v2;
    default:  // Unknown operator, return 0
      return 0;
    }
  }
}

// Deletes the entire tree (the root and the subtrees)
void DeleteTree(TreeNode * tree)
{
  if (tree!=NULL) {
    DeleteTree (tree->left);
    DeleteTree (tree->right);
    delete tree;
  }
}

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 '-':     // by popping two operands and creating a new
    case '*':     // tree out of them
    case '/':
      if(!s.Pop(v1)) {
        cout<<"Stack Empty!\n";
	break;
      }
      if(!s.Pop(v2)) {
	s.Push(v1);  // Resore first operand to stack if second Pop fails
        cout<<"Stack Has Only One Entry!\n";
	break;
      }
      else if ((v3=new TreeNode(c, v2, v1))==NULL) { // Create a new tree
	cout<<"Out of Memory\n";                     // out of the two on top
	s.Push(v2);                                  // If it fails, restore
	s.Push(v1);                                  // the stack
      }
      else if (!s.Push(v3))
	cout<<"Stack Overflow!\n";
      break;

    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;
}