打卡cs106x(Autumn 2017)-lecture5
(以下皆使用SPL实现，非STL库，后续课程结束会使用STL实现)
1、stackMystery1
What is the output of the following code?
Stack<int> s;
s.push(7);
s.push(10);
cout << s.peek() << " ";
cout << s.pop() << " ";
s.push(3);
s.push(5);
cout << s.pop() << " ";
cout << s.size() << " ";
cout << s.peek() << " ";
s.push(8);
cout << s.pop() << " ";
cout << s.pop() << " ";解答：
10 10 5 2 3 8 3
2、checkBalance
Write a function named checkBalance that accepts a string of source code and uses a Stack to check whether the braces/parentheses are balanced. Every ( or { must be closed by a } or ) in the opposite order. Return the index at which an imbalance occurs, or -1 if the string is balanced. If any ( or { are never closed, return the string's length.
Here are some example calls:
Constraints: Use a single stack as auxiliary storage.
解答：
#include <iostream>
#include <string>
#include "console.h"
#include "stack.h"using namespace std;int checkBalance(string code);int main() {cout << checkBalance("if (a(4) > 9) { foo(a(2)); }") << endl;cout << checkBalance("for (i=0;i<a(3};i++) { foo{); )") << endl;cout << checkBalance("while (true) foo(); }{ ()") << endl;cout << checkBalance("if (x) {") << endl;return 0;
}int checkBalance(string code) {Stack<char> s;int len = code.length();for (int i = 0; i < len; i++) {if (code[i] == '(' || code[i] == '{') {s.push(code[i]);} else if (code[i] == ')' || code[i] == '}') {if (s.isEmpty()) {return i;}char top = s.pop();bool p1 = (code[i] == ')' && top != '(');bool p2 = (code[i] == '}' && top != '{');if (p1 || p2) {return i;}}}if (s.isEmpty()) {return -1;} else {return len;}
}3、queueMystery1
What is the output of the following code?
解答：
1 2 3 {4, 5, 6} size 3
4、stutter
Write a function named stutter that accepts a reference to a queue of integers as a parameter and replaces every element with two copies of itself. For example, if a queue named q stores {1, 2, 3}, the call of stutter(q); should change it to store {1, 1, 2, 2, 3, 3}.
Constraints: Do not use any auxiliary collections as storage.
解答：
#include <iostream>
#include "console.h"
#include "queue.h"using namespace std;void stutter(Queue<int>& q);int main() {Queue<int> q {1, 2, 3};stutter(q);cout << q;return 0;
}void stutter(Queue<int>& q) {int len = q.size();for (int i = 0; i < len; i++) {int element = q.dequeue();q.enqueue(element);q.enqueue(element);}
}5、mirror
Write a function named mirror that accepts a reference to a queue of strings as a parameter and appends the queue's contents to itself in reverse order. For example, if a queue named q stores {"a", "b", "c"}, the call of mirror(q); should change it to store {"a", "b", "c", "c", "b", "a"}.
Constraints: You may declare a single stack or queue as auxiliary storage.
解答：
#include <iostream>
#include <string>
#include "console.h"
#include "queue.h"
#include "stack.h"using namespace std;void mirror(Queue<string>& q);int main() {Queue<string> q {"a", "b", "c"};mirror(q);cout << q;return 0;
}void mirror(Queue<string>& q) {Stack<string> s;int len = q.size();for (int i = 0; i < len; i++) {string element = q.dequeue();s.push(element);q.enqueue(element);}while (!s.isEmpty()) {q.enqueue(s.pop());}
}