// Simple Stack Example
#include <iostream>
#include "console.h"
#include "stack.h"

using namespace std;
const char SPACE = ' ';

int main() {
    string sentence = "hope is what defines humanity";
    string word;
    Stack<string> wordStack;

    cout << "Original sentence: " << sentence << endl;

    for (char c : sentence) {
       if (c == SPACE and word != "") {
           wordStack.push(word);
           word = ""; // reset
       }
       else {
           word += c;
       }
    }
    if (word != "") {
        wordStack.push(word);
    }

    cout << "     New sentence: ";
    while (!wordStack.isEmpty()) {
        string word = wordStack.pop();
        cout << word << SPACE;
    }
    cout << endl;
    return 0;
}

// Queue mystery
#include <iostream>
#include "console.h"
#include "simpio.h"
#include "queue.h"

using namespace std;

int main() {
    Queue<int> queue;
    // produce: {1, 2, 3, 4, 5, 6}
    for (int i = 1; i <= 6; i++) {
        queue.enqueue(i);
    }
    // original mystery:
    for (int i = 0; i < queue.size(); i++) {
        cout << queue.dequeue() << " ";
    }

    // better idiom:
//    while (!queue.isEmpty()) {
//        cout << queue.dequeue() << " ";
//    }

    // okay idiom if you want to go through original queue elements once:
//     int origQSize = queue.size();
//     for (int i=0; i < origQSize; i++) {
//         int value = queue.dequeue();
//         cout << value << " ";
//         // re-enqueue even values
//         if (value % 2 == 0) {
//             queue.enqueue(value);
//         }
//     }

    cout << queue.toString() << "  size " << queue.size() << endl;
    return 0;
}


// Postfix arithmetic, implementing +, -, *, /

#include <iostream>
#include "console.h"
#include "simpio.h"
#include "stack.h"

using namespace std;

const string OPERATORS = "+-*x/";
const string SEPARATOR = " ";

// function prototypes
double parsePostfix(string expression);
string getNextToken(string &expression);
void performCalculation(Stack<double> &s, char op);

int main() {
    string expression;
    double answer;
    do {
        expression = getLine("Please enter a postfix expression (blank to quit): ");
        answer = parsePostfix(expression);
        cout << "The answer is: " << answer << endl << endl;
    } while (expression != "");
    return 0;
}

double parsePostfix(string expression) {
    Stack<double> s;
    string nextToken;

    while (expression != "") {
        // gets the next token and removes it from expression
        nextToken = getNextToken(expression);
        if (OPERATORS.find(nextToken) == string::npos) {
            // we have a number
            double operand = stringToDouble(nextToken);
            s.push(operand);
        }
        else {
            // we have an operator
            char op = stringToChar(nextToken);
            performCalculation(s,op);
        }
    }
    return s.pop();
}

void performCalculation(Stack<double> &s, char op) {
    double result;
    double operand2 = s.pop(); // LIFO!
    double operand1 = s.pop();
    switch(op) {
        case '+': result = operand1 + operand2;
                  break;
        case '-': result = operand1 - operand2;
                  break;
        // allow "*" or "x" for times
        case '*':
        case 'x': result = operand1 * operand2;
                  break;
        case '/': result = operand1 / operand2;
                  break;
    }
    s.push(result);
}

string getNextToken(string &expression) {
    // pull out the substring up to the first space
    // and return the token, removing it from the expression
    string token;
    int sepLoc = expression.find(SEPARATOR);
    if (sepLoc != (int) string::npos) {
        token = expression.substr(0,sepLoc);
        expression = expression.substr(sepLoc+1,expression.size()-sepLoc);
        return token;
    }
    else {
        token = expression;
        expression = "";
        return token;
    }
}

// Match symbols using a stack
#include <iostream>
#include <cmath>
#include "console.h"
#include "simpio.h"  // for getLine
#include "stack.h"

using namespace std;

// function prototypes
string getInput();
bool bracketsMatch(string input, char &unmatched);
bool closingBracketOkay(char c, Stack<char> &s);
void printInputWithLines(string input);
void printSpaces(int n);

// constants
const string openingBrackets = "{[(";
const string closingBrackets = "}])";

int main() {
    string input = getInput();
    char unmatched;
    cout << "The input:" << endl << endl;
    printInputWithLines(input);
    if (bracketsMatch(input,unmatched)) {
        cout << "All brackets match!" << endl;
    } else {
        cout << "The following symbol didn't match: " << unmatched << endl;
    }
    return 0;
}

string getInput() {
    string allInput;
    string oneLine;
    cout << "This program will determine if your brackets are matched." << endl;
    cout << "Please enter program code, followed by a period on a line by itself." << endl;

    oneLine = getLine();
    while (oneLine != ".") {
       allInput += oneLine + "\n";
       oneLine = getLine();
    }
    return allInput;
}

bool bracketsMatch(string input, char &unmatched) {
    Stack<char> s;

    for (char c : input) {
        // look for opening brackets
        if (openingBrackets.find(c) != string::npos) {
            s.push(c);
        }
        else {
            // look for closing brackets
            if (!closingBracketOkay(c,s)) {
                    unmatched = c;
                    return false;
            }
        }
    }
    // if we made it through the characters and the stack is not empty,
    // then we don't have a match :(
    if (!s.isEmpty()) {
        // report the top of the stack
        unmatched = s.pop();
        return false;
    }
    // We made it!
    return true;
}

bool closingBracketOkay(char c, Stack<char> &s) {
    char leftSymbol;

    // look for closing brackets
    if (closingBrackets.find(c) != string::npos) {
       if (s.isEmpty()) { // uh-oh!
           return false;
       }
       else {
           leftSymbol = s.pop();
           // check to see if the symbols are the same type
           if (openingBrackets.find(leftSymbol) != closingBrackets.find(c)) {
               // nope! :(
               return false;
           }
       }
    }
    return true;
}

void printInputWithLines(string input) {
    // count the number of lines
    int numLines = 1;
    for (char c : input) {
       if (c == '\n') {
           numLines++;
       }
    }
    // the log_10(numLines) is the maximum number of digits
    int maxDigits = log(numLines) / log(10);

    int lineNum = 0; // the first line
    int numDigits;
    for (char c : input) {
       if (lineNum == 0 || c == '\n') {
           if (lineNum != 0) {
               cout << endl;
           }
           lineNum++;
           numDigits = log(lineNum) / log(10);
           printSpaces(maxDigits - numDigits);
           cout << lineNum << "  ";
           if (lineNum == 1) {
               cout << c; // first character is special
           }
       }
       else {
           cout << c;
       }
    }
    cout << endl;
}

void printSpaces(int n) {
    for (int i=0; i < n; i++) {
        cout << " ";
    }
}