csce420pine64backup/hw2/hw2pr2/hw2pr2.cpp

// Name: Alexander Huddleston UIN: 223000555
// CSCE 420
// Due: 11:59 P.M. Monday, October 30, 2017
// hw2pr1.cpp

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <limits.h>
#include <tuple>
#include "node.h"

using namespace std;

// Perform min/max on this tree.
void minmax(node *n)
{

    if(n->getLevel() % 2 == 0)
    {
        int max = n->getValue();
        
        if(n->getChildren().size() > 0)
        {
            for(int c = 0; c < n->getChildren().size(); c++)
            {
        	    n->getChildAt(c)->setBeta(n->getBeta());
        	    n->getChildAt(c)->setAlpha(n->getAlpha());
		
		        //cout << "Alpha: " << n->getAlpha() << " Beta: " << n->getBeta() << endl;
                
		        minmax(n->getChildAt(c));

                if(n->getChildAt(c)->getValue() > max)
                {
                    max = n->getChildAt(c)->getValue();
                }

		        if(n->getChildAt(c)->getValue() > n->getAlpha())
		        {
		            n->setAlpha(n->getChildAt(c)->getValue());
		        }

		        if(n->getAlpha() >= n->getBeta())
		        {
		            cout << "Beta pruning" << endl;
		            break;
		        }
            }
        }

        n->setValue(max);
    }

    else
    {
        int min = n->getValue();
        if(n->getChildren().size() > 0)
        {
            for(int c = 0; c < n->getChildren().size(); c++)
            {
            	n->getChildAt(c)->setBeta(n->getBeta());
            	n->getChildAt(c)->setAlpha(n->getAlpha());
		
		        //cout << "Alpha: " << n->getAlpha() << " Beta: " << n->getBeta() << endl;
                
		        minmax(n->getChildAt(c));
                
                if(n->getChildAt(c)->getValue() < min)
                {
                    min = n->getChildAt(c)->getValue();
                }

		        if(n->getChildAt(c)->getValue() < n->getBeta())
		        {
		            n->setBeta(n->getChildAt(c)->getValue());
		        }
		
		        if(n->getBeta() <= n->getAlpha())
		        {
		            cout << "Alpha pruning." << endl;
		            break;
		        }
            }
        }

        n->setValue(min);
    }
}

// This is mostly just a simple debug function so I can see
// if my tree is being formed properly.
void printTree(node n)
{
    cout << n.getValue() << " " << n.getLevel() << " ";
    if(n.getChildren().size() != 0)
    {
        cout << "\n|\n";
        for(node c : n.getChildren())
        {
            printTree(c);
        }
        cout << endl;
    }
}

tuple<node, string> makeTree(string input, node n, int level)
{
    bool negate = false;
    char tempc;
    string tempn = "";

    while(input.length() != 0)
    {
        tempc = input[0];
        if(input.length() > 0)
        {
            input = input.substr(1);
        }
        else
        {
            input = "";
        }

        // If the char is a number.
        if(isdigit(tempc))
        {
            tempn += tempc;
        }

	else if(tempc == '-')
	{
	    negate = true;
	}
        
        // If the char is a comma.
        else if(tempc == ',')
        {
            if(tempn.length() > 0)
            {
                node tempnode;
                tempnode.setLevel(level);
		        int negatemp = stoi(tempn);
		        if(negate)
		        {
		            negatemp = -negatemp;
		        }
                tempnode.setValue(negatemp);
                tempnode.setParent(&n);
                n.addChild(tempnode);
                tempn = "";
		        negate = false;
            }
        }

        // If the char is a close paranthesis.
        else if(tempc == ')')
        {
            if(tempn.length() > 0)
            {
                node tempnode;
                tempnode.setLevel(level);
		        int negatemp = stoi(tempn);
		        if(negate)
		        {
		            negatemp = -negatemp;
		        }
                tempnode.setValue(negatemp);
                tempnode.setParent(&n);
                n.addChild(tempnode);
                tempn = "";
		        negate = false;
            }
            tuple<node, string> tempt(n, input);
            return tempt;
        }

        // If the char is an open paranthesis.
        else if(tempc == '(')
        {
            node tempnode;
            tempnode.setLevel(level);
            if(level % 2 == 0)
            {
                tempnode.setValue(INT_MIN);
            }
            else
            {
                tempnode.setValue(INT_MAX);
            }
            tempnode.setParent(&n);
            tuple<node, string> tempt = makeTree(input, tempnode, level + 1);
            tempnode = get<0>(tempt);
            input = get<1>(tempt);
            n.addChild(tempnode);
        }
    }

    tuple<node, string> output(n, input);
    return output;
}

int main(int argc, char **argv)
{
    // Initialization of input string.
    string input = "";

    // For testing, I want to read from a file.
    // Typing in an tree from the keyboard each execution is a waste of time.
    if(argc > 1)
    {
        if(!((string)argv[1]).substr(0, 2).compare("-f"))
        {
            ifstream file;
            string line;
            try
            {
                file.open("hw2pr2_data.txt");
            }
            catch(exception e)
            {
                cerr << "File not found, or could not be opened." << endl;
            }
            while(!file.eof())
            {
                getline(file, line);
                input += line;
            }
        }
    }

    else
    {
        cout << "Please input a tree: ";
        cin >> input;
    }

    node root;
    root.setLevel(0);
    root.setValue(INT_MIN);
    tuple<node, string> tree;
    tree = makeTree(input.substr(1), root, 1);
    root = get<0>(tree);

    //printTree(root);
    minmax(&root);

    //printTree(root);
    cout << root.getValue() << endl;

    return 0;
}