from jupyterquiz import display_quiz

path = "questions/ch5/"

template <typename T>
class Stack {
    private:
        vector<T> items;

    public:
        bool isEmpty() {
            return items.empty();
        }
        void push(T item) {
            items.push_back(item);
        }
        int size() {
            return items.size();
        }
};

T pop() {
    T top = items.back();
    items.pop_back();
    return top;
}
T peek() {
    return items.back();
}
void display() {
    for (T x : items) cout << x << " ";
    cout << endl;
}

#include <iostream>
#include "dscpp/stack.hpp"   // the vector-backed Stack of this section
using namespace std;

int main() {
    Stack<double> s;
    cout << boolalpha << s.isEmpty() << endl;
    s.push(4);
    s.push(7.5);
    cout << s.peek() << endl;
    s.push(8.4);
    s.display();
    cout << s.pop() << endl;
    cout << s.size() << endl;
    return 0;
}

template <typename T>
class Stack2 {
    private:
        vector<T> items;

    public:
        bool isEmpty() {
            return items.empty();
        }
        void push(T item) {
            items.insert(items.begin(), item);   // O(n)!
        }
        T pop() {
            T top = items.front();
            items.erase(items.begin());   // O(n)!
            return top;
        }
        T peek() {
            return items.front();
        }
        int size() {
            return items.size();
        }
};

#include <iostream>
#include "dscpp/stack.hpp"   // Stack2: top at the front, O(n) ops
using namespace std;

int main() {
    Stack2<double> s;
    cout << boolalpha << s.isEmpty() << endl;
    s.push(4);
    s.push(7.5);
    cout << s.peek() << endl;
    s.push(2);
    cout << s.size() << endl;
    cout << s.pop() << endl;
    cout << s.pop() << endl;
    cout << s.size() << endl;
    return 0;
}

display_quiz(path+"stack1.json", max_width=800)

/tmp/tmpl39zn56s.cpp: In function ‘std::string revString(std::string)’:
/tmp/tmpl39zn56s.cpp:13:5: error: expected primary-expression before ‘}’ token
   13 |     }
      |     ^

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

display_quiz(path+"stack2.json", max_width=800)

/tmp/tmpl39zn56s.cpp: In function ‘std::string revString(std::string)’:
/tmp/tmpl39zn56s.cpp:13:5: error: expected primary-expression before ‘}’ token
   13 |     }
      |     ^

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

#include <iostream>
#include <stack>
using namespace std;

string revString(string myStr) {
    stack<char> s;
    // Step 1: push every char onto s;  Step 2: pop to build rStr
    string rStr = "";
    while (!s.empty()) {
        rStr = 
    }
    return rStr;
}

int main() {
    cout << revString("NSYSU") << endl;
    return 0;
}

/tmp/tmpl39zn56s.cpp: In function ‘std::string revString(std::string)’:
/tmp/tmpl39zn56s.cpp:13:5: error: expected primary-expression before ‘}’ token
   13 |     }
      |     ^

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool parChecker(string symbolString) {
    stack<char> s;
    for (char symbol : symbolString) {
        if (symbol == '(') {
            s.push(symbol);
        } else {
            if (s.empty()) {
                return false;
            } else {
                s.pop();
            }
        }
    }
    return s.empty();
}

int main() {
    cout << boolalpha;
    cout << parChecker("((()))") << endl;    // expected true
    cout << parChecker("((()()))") << endl;  // expected true
    cout << parChecker("(()") << endl;       // expected false
    cout << parChecker(")(") << endl;        // expected false
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool matches(char symLeft, char symRight) {
    string allLefts = "([{";
    string allRights = ")]}";
    return allLefts.find(symLeft) == allRights.find(symRight);
}

bool balanceChecker(string symbolString) {
    stack<char> s;
    for (char symbol : symbolString) {
        if (symbol == '(' || symbol == '[' || symbol == '{') {
            s.push(symbol);
        } else {
            if (s.empty()) {
                return false;
            } else {
                char top = s.top();
                s.pop();
                if (!matches(top, symbol)) {
                    return false;
                }
            }
        }
    }
    return s.empty();
}

int main() {
    cout << boolalpha;
    cout << balanceChecker("{({([][])}())}") << endl;  // expected true
    cout << balanceChecker("[{()]") << endl;           // expected false
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string divideBy2(int decimalNum) {
    stack<int> remStack;
    while (decimalNum > 0) {
        remStack.push(decimalNum % 2);
        decimalNum = decimalNum / 2;
    }
    string binString = "";
    while (!remStack.empty()) {
        binString += to_string(remStack.top());
        remStack.pop();
    }
    return binString;
}

int main() {
    cout << divideBy2(42) << " " << divideBy2(31) << endl;
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;

string baseConverter(int decimalNum, int base) {
    string digits = "0123456789ABCDEF";
    stack<int> remStack;
    while (decimalNum > 0) {
        remStack.push(decimalNum % base);  decimalNum /= base;
    }
    string newString = "";
    while (!remStack.empty()) {
        newString += digits[remStack.top()];  remStack.pop();
    }
    return newString;
}

int main() {
    cout << baseConverter(25, 2) << " " << baseConverter(25, 16) << endl;
    return 0;
}

display_quiz(path+"convert.json", max_width=800)

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

for (string token : tokenList) {
    if (isalnum(token[0])) {
        postfixList.push_back(token);
    } else if (token == "(") {
        opStack.push(token);
    } else if (token == ")") {
        while (!opStack.empty() && opStack.top() != "(") {
            postfixList.push_back(opStack.top());
            opStack.pop();
        }
        opStack.pop();   // pop the "("
    } else {
        while (!opStack.empty() && prec[opStack.top()] >= prec[token]) {
            postfixList.push_back(opStack.top());
            opStack.pop();
        }
        opStack.push(token);
    }
}

#include <iostream>
#include "dscpp/expression.hpp"   // the complete converter (md listing above)
using namespace std;

int main() {
    cout << infixToPostfix("A * B + C * D") << endl;
    cout << infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )") << endl;
    return 0;
}

double doMath(string op, double op1, double op2) {
    if (op == "*") {
        return op1 * op2;
    } else if (op == "/") {
        return op1 / op2;
    } else if (op == "+") {
        return op1 + op2;
    } else {
        return op1 - op2;
    }
}

#include <iostream>
#include "dscpp/expression.hpp"   // doMath + postfixEval
using namespace std;

int main() {
    cout << postfixEval("7 8 + 3 2 + /") << endl;
    return 0;
}

display_quiz(path+"c1.json", max_width=800)

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

display_quiz(path+"c2.json", max_width=800)

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

#include <iostream>
#include <stack>
#include <vector>
#include <map>
#include <sstream>
#include <string>
#include <cctype>
using namespace std;

string infixToPostfix(string infixExpr) {
    // Your code here: add support for the right-associative ^ operator

    return result;
}

int main() {
    cout << infixToPostfix("5 * 3 ^ ( 4 - 2 )") << endl;
    return 0;
}

/tmp/tmpnuhnarzj.cpp: In function ‘std::string infixToPostfix(std::string)’:
/tmp/tmpnuhnarzj.cpp:15:12: error: ‘result’ was not declared in this scope
   15 |     return result;
      |            ^~~~~~

[C++ kernel] Error: Unable to compile the source code. Return error: 0x1.

template <typename T>
class Queue {
    private:
        vector<T> items;

    public:
        bool isEmpty() {
            return items.empty();
        }
        void enqueue(T item) {
            items.insert(items.begin(), item);   // rear at position 0
        }
        T dequeue() {
            T front = items.back();
            items.pop_back();
            return front;
        }
        int size() {
            return items.size();
        }
};

#include <iostream>
#include "dscpp/queue.hpp"   // the vector-backed Queue of this section
using namespace std;

int main() {
    Queue<string> q;
    q.enqueue("4");
    q.enqueue("dog");
    q.enqueue("true");
    cout << q.size() << endl;
    cout << boolalpha << q.isEmpty() << endl;
    cout << q.dequeue() << endl;
    return 0;
}

display_quiz(path+"queue.json", max_width=800)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// STL queue: front() reads, pop() removes (returns nothing)
string hotPotato(vector<string> nameList, int num) {
    queue<string> simQueue;
    for (string name : nameList) simQueue.push(name);
    while (simQueue.size() > 1) {
        for (int i = 0; i < num; i++) {
            simQueue.push(simQueue.front());
            simQueue.pop();
        }
        simQueue.pop();
    }
    return simQueue.front();
}

int main() {
    cout << hotPotato({"Bill", "David", "Susan", "Jane", "Kent", "Brad"}, 7) << endl;
    return 0;
}

// Your code here

class Printer {
    private:
        int pageRate;
        Task* currentTask;
        double timeRemaining;

    public:
        Printer(int ppm) {
            pageRate = ppm;
            currentTask = NULL;
            timeRemaining = 0;
        }
        void tick() {
            if (currentTask != NULL) {
                timeRemaining -= 1;
                if (timeRemaining <= 0) {
                    currentTask = NULL;
                }
            }
        }
        bool busy() {
            return currentTask != NULL;
        }
        void startNext(Task* newTask) {
            currentTask = newTask;
            timeRemaining = newTask->getPages() * 60.0 / pageRate;
        }
};

class Task {
    private:
        int timestamp;
        int pages;

    public:
        Task(int time) {
            timestamp = time;
            pages = rand() % 20 + 1;
        }
        int getStamp() { return timestamp; }
        int getPages() { return pages; }
        int waitTime(int currentTime) {
            return currentTime - timestamp;
        }
};

void simulation(int numSeconds, int pagesPerMinute) {
    Printer labPrinter(pagesPerMinute);
    queue<Task*> printQueue;
    vector<int> waitingTimes;

    for (int currentSecond = 0; currentSecond < numSeconds; currentSecond++) {
        if (newPrintTask()) {
            printQueue.push(new Task(currentSecond));
        }

        if (!labPrinter.busy() && !printQueue.empty()) {
            Task* nextTask = printQueue.front();
            printQueue.pop();
            waitingTimes.push_back(nextTask->waitTime(currentSecond));
            labPrinter.startNext(nextTask);
        }

        labPrinter.tick();
    }

    double sum = 0;
    for (int w : waitingTimes) sum += w;
    printf("Average Wait %6.2f secs %3d tasks remaining.\n",
           sum / waitingTimes.size(), (int)printQueue.size());
}

#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
using namespace std;

class Task {
    private:
        int timestamp;
        int pages;
    public:
        Task(int time) { timestamp = time; pages = rand() % 20 + 1; }
        int getPages() { return pages; }
        int waitTime(int currentTime) { return currentTime - timestamp; }
};

class Printer {
    private:
        int pageRate;
        Task* currentTask;
        double timeRemaining;
    public:
        Printer(int ppm) { pageRate = ppm; currentTask = NULL; timeRemaining = 0; }
        void tick() {
            if (currentTask != NULL) {
                timeRemaining -= 1;
                if (timeRemaining <= 0) { delete currentTask; currentTask = NULL; }
            }
        }
        bool busy() { return currentTask != NULL; }
        void startNext(Task* newTask) {
            currentTask = newTask;
            timeRemaining = newTask->getPages() * 60.0 / pageRate;
        }
};

bool newPrintTask() {
    return rand() % 180 + 1 == 180;
}

void simulation(int numSeconds, int pagesPerMinute) {
    Printer labPrinter(pagesPerMinute);
    queue<Task*> printQueue;
    vector<int> waitingTimes;

    for (int currentSecond = 0; currentSecond < numSeconds; currentSecond++) {
        if (newPrintTask()) {
            printQueue.push(new Task(currentSecond));
        }
        if (!labPrinter.busy() && !printQueue.empty()) {
            Task* nextTask = printQueue.front();
            printQueue.pop();
            waitingTimes.push_back(nextTask->waitTime(currentSecond));
            labPrinter.startNext(nextTask);
        }
        labPrinter.tick();
    }

    double sum = 0;
    for (int w : waitingTimes) sum += w;
    printf("Average Wait %6.2f secs %3d tasks remaining.\n",
           waitingTimes.empty() ? 0 : sum / waitingTimes.size(), (int)printQueue.size());
}

int main() {
    srand(42);
    cout << "pages per minute = 5:" << endl;
    for (int i = 0; i < 10; i++) simulation(3600, 5);

    cout << "pages per minute = 10:" << endl;
    for (int i = 0; i < 10; i++) simulation(3600, 10);
    return 0;
}

template <typename T>
class Deque {
    private:
        vector<T> items;

    public:
        bool isEmpty() {
            return items.empty();
        }
        void addFront(T item) {
            items.push_back(item);
        }
        void addRear(T item) {
            items.insert(items.begin(), item);
        }
};

T removeFront() {
    T front = items.back();
    items.pop_back();
    return front;
}
T removeRear() {
    T rear = items.front();
    items.erase(items.begin());
    return rear;
}
int size() {
    return items.size();
}

#include <iostream>
#include <deque>
#include <string>
using namespace std;

bool palChecker(string aString) {
    deque<char> charDeque;
    for (char ch : aString) charDeque.push_back(ch);   // add to the rear
    while (charDeque.size() > 1) {
        char first = charDeque.front(); charDeque.pop_front();
        char last = charDeque.back(); charDeque.pop_back();
        if (first != last) return false;
    }
    return true;
}

int main() {
    cout << boolalpha;
    cout << palChecker("lsdkjfskf") << endl;   // false
    cout << palChecker("radar") << endl;       // true
    return 0;
}

from jupytercards import display_flashcards
fpath = "flashcards/"
display_flashcards(fpath + 'ch5.json')

Stack Operation	Stack Contents	Return Value
`s.is_empty()`	[]	True
`s.push(4)`	[4]
`s.push('dog')`	[4, 'dog']
`s.peek()`	[4, 'dog']	'dog'
`s.push(True)`	[4, 'dog', True]
`s.size()`	[4, 'dog', True]	3
`s.is_empty()`	[4, 'dog', True]	False
`s.push(8.4)`	[4, 'dog', True, 8.4]
`s.pop()`	[4, 'dog', True]	8.4
`s.pop()`	[4, 'dog']	True
`s.size()`	[4, 'dog']	2

Infix Expression	Prefix Expression	Postfix Expression
`A + B`	`+ A B`	`A B +`
`A + B · C`	`+ A · B C`	`A B C · +`
`(A + B) · C`	`· + A B C`	`A B + C ·`
`A + B · C + D`	`+ + A · B C D`	`A B C · + D +`
`(A + B) · (C + D)`	`· + A B + C D`	`A B + C D + ·`
`A · B + C · D`	`+ · A B · C D`	`A B · C D · +`
`A + B + C + D`	`+ + + A B C D`	`A B + C + D +`

Queue Operation	Queue Contents	Return Value
`q.is_empty()`	[]	True
`q.enqueue(4)`	[4]
`q.enqueue("dog")`	['dog', 4]
`q.enqueue(True)`	[True, 'dog', 4]
`q.size()`	[True, 'dog', 4]	3
`q.is_empty()`	[True, 'dog', 4]	False
`q.enqueue(8.4)`	[8.4, True, 'dog', 4]
`q.dequeue()`	[8.4, True, 'dog']	4
`q.dequeue()`	[8.4, True]	'dog'
`q.size()`	[8.4, True]	2

Deque Operation	Deque Contents	Return Value
`d.is_empty()`	[]	True
`d.add_rear(4)`	[4]
`d.add_rear("dog")`	['dog', 4]
`d.add_front("cat")`	['dog', 4, 'cat']
`d.add_front(True)`	['dog', 4, 'cat', True]
`d.size()`	['dog', 4, 'cat', True]	4
`d.is_empty()`	['dog', 4, 'cat', True]	False
`d.add_rear(8.4)`	[8.4, 'dog', 4, 'cat', True]
`d.remove_rear()`	['dog', 4, 'cat', True]	8.4
`d.remove_front()`	['dog', 4, 'cat']	True

Linear Structure¶

3.1~3.2 What Are Linear ADT?¶

3.3 Stacks¶

3.4 The Stack Abstract Data Type¶

3.5 Implementing a Stack in `C++`¶

Exercise: Write a function `rev_string(my_str)` that uses a stack to reverse the characters in a string.¶

3.6. Simple Balanced Parentheses¶

3.7. Balanced Symbols (A General Case)¶

3.8. Converting Decimal Numbers to Binary Numbers¶

3.9. Infix, Prefix, and Postfix Expressions¶

3.9.1 Conversion of Infix Expressions to Prefix and Postfix¶

3.9.2. General Infix-to-Postfix Conversion¶

3.9.3. Postfix Evaluation¶

Exercise: Modify the `infix_to_postfix()` function so that it can convert the following expression: `5 * 3 ^ (4 - 2)`. Run the function on the expression and paste the answer here:¶

3.10. Queues¶

3.11 The Queue Abstract Data Type¶

3.12 Implementing a Queue in `C++`¶

3.13. Queue Simulation: Hot Potato¶

Exercise: Implement the queue ADT, using a list such that the rear of the queue is at the end of the list.¶

3.14. Queue Simulation: Printing Tasks¶

3.14.1. Main Simulation Steps¶

3.14.2. Python Implementation¶

3.14.3. Discussion¶

3.15 Deques¶

3.16 The Deque Abstract Data Type¶

3.17. Implementing a Deque in `C++`¶

3.18 Palindrome Checker¶

References¶

Key terms¶

Linear Structure¶

3.1~3.2 What Are Linear ADT?¶

3.3 Stacks¶

3.4 The Stack Abstract Data Type¶

3.5 Implementing a Stack in C++¶

Exercise: Write a function rev_string(my_str) that uses a stack to reverse the characters in a string.¶

3.6. Simple Balanced Parentheses¶

3.7. Balanced Symbols (A General Case)¶

3.8. Converting Decimal Numbers to Binary Numbers¶

3.9. Infix, Prefix, and Postfix Expressions¶

3.9.1 Conversion of Infix Expressions to Prefix and Postfix¶

3.9.2. General Infix-to-Postfix Conversion¶

3.9.3. Postfix Evaluation¶

Exercise: Modify the infix_to_postfix() function so that it can convert the following expression: 5 * 3 ^ (4 - 2). Run the function on the expression and paste the answer here:¶

3.10. Queues¶

3.11 The Queue Abstract Data Type¶

3.12 Implementing a Queue in C++¶

3.13. Queue Simulation: Hot Potato¶

Exercise: Implement the queue ADT, using a list such that the rear of the queue is at the end of the list.¶

3.14. Queue Simulation: Printing Tasks¶

3.14.1. Main Simulation Steps¶

3.14.2. Python Implementation¶

3.14.3. Discussion¶

3.15 Deques¶

3.16 The Deque Abstract Data Type¶

3.17. Implementing a Deque in C++¶

3.18 Palindrome Checker¶

References¶

Key terms¶

3.5 Implementing a Stack in `C++`¶

Exercise: Write a function `rev_string(my_str)` that uses a stack to reverse the characters in a string.¶

Exercise: Modify the `infix_to_postfix()` function so that it can convert the following expression: `5 * 3 ^ (4 - 2)`. Run the function on the expression and paste the answer here:¶

3.12 Implementing a Queue in `C++`¶

3.17. Implementing a Deque in `C++`¶