Two-stack calculators and string decoding

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <cctype> #include <iostream> #include <stack> #include <string> std::string decode(const std::string& s) { struct Frame { int repeat; std::string prefix; }; std::stack<Frame> frames; std::string current; int number = 0; for (char c : s) { if (std::isdigit(static_cast<unsigned char>(c))) { number = number * 10 + (c - '0'); } else if (c == '[') { frames.push({number, current}); number = 0; current.clear(); } else if (c == ']') { Frame f = frames.top(); frames.pop(); std::string block; for (int i = 0; i < f.repeat; ++i) { block += current; } current = f.prefix + block; } else { current += c; } } return current; } int main() { std::cout << decode("3[x2[y]]z") << '\n'; } ``

   xyxyxyzxyyxyyzxyyxyyxyyzxxxyyyz
2. 2. In the decoder, what happens when a ] is read?

   A new frame is pushed with the current number and textThe top frame is popped, the current text is repeated its count times, and the saved text is put in frontThe number is cleared and the current text is keptThe top frame is popped and the current text is thrown away
3. 3. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <string> #include <string_view> #include <vector> std::string simplify_path(std::string_view path) { std::vector<std::string> stack; std::string part; for (std::size_t i = 0; i <= path.size(); ++i) { char c = i < path.size() ? path[i] : '/'; if (c != '/') { part += c; continue; } if (part.empty() || part == ".") { // nothing to do } else if (part == "..") { if (!stack.empty()) { stack.pop_back(); } } else { stack.push_back(part); } part.clear(); } std::string result; for (const auto& name : stack) { result += "/" + name; } return result.empty() ? "/" : result; } int main() { std::cout << simplify_path("/x/y/../../../z/./") << '\n'; } ``

   /x/z//../z/z
4. 4. What does this program print? ``cpp #include <iostream> #include <stack> #include <string> int precedence(char op) { return (op == '*' || op == '/') ? 2 : 1; } void apply(std::stack<long long>& values, char op) { long long right = values.top(); values.pop(); long long left = values.top(); values.pop(); switch (op) { case '+': values.push(left + right); break; case '-': values.push(left - right); break; case '*': values.push(left * right); break; default: values.push(left / right); break; } } long long evaluate(const std::string& text) { std::stack<long long> values; std::stack<char> ops; for (char c : text) { if (c == ' ') continue; if (c >= '0' && c <= '9') { values.push(c - '0'); } else { while (!ops.empty() && precedence(ops.top()) >= precedence(c)) { apply(values, ops.top()); ops.pop(); } ops.push(c); } } while (!ops.empty()) { apply(values, ops.top()); ops.pop(); } return values.top(); } int main() { std::cout << evaluate("9 - 6 / 2 * 4 - 1") << '\n'; } ``

   -43-34
5. 5. A student reorders the ] branch of decode like this: ``cpp } else if (c == ']') { Frame f = frames.top(); if (frames.empty()) { throw std::invalid_argument("unmatched ']'"); } frames.pop(); // repeat current and join f.prefix, as before } `` What is wrong with it?

   Nothing; top() on an empty stack returns a default frame, so the check is not neededThe throw must use std::domain_error instead of std::invalid_argumenttop() runs before the empty check, so input such as a] calls top() on an empty stack, which is undefined behaviourThe pop must come before top(), or the frame is lost