Balanced Brackets

Solutions Stack This is a classical problem which requires a stack. Possible C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <stack>#include <map>#include <iostream>using namespace std; static const map<char, char> closedParen { {')', '('}, {']', '[',}, {'}', '{'} }; int main() { int N; cin >> N; string line; while (N--) { stack<char> paren; bool error = false; cin >> line; for (auto c : line) { if (c == '(' || c == '[' || c == '{') paren. [Read More]
stack 

Evaluate Expression

You are given an expression in Reverse Polish Notation (RPN) and you have to evaluate it. Input Format Space separated terms of the expression to evaluate (at least one element). Constraints Each numeric element fits an int32. Any other token is either +, -, *, / The result is guaranteed not to go beyond the int32 representation Output Format The result of the expression evaluation, as a single number. [Read More]

Queue Using Two Stacks

Preamble This is a typical challenge where the environment we have to work in is constrained and we have to find a solution under some conditions. Same story when we are not allowed to allocate extra space, or when some basic operation is disabled (e.g. for loop). Why “constrained” challenges make perfect sense Although such challenges could seem senseless, they are instead very useful to improve our ability to adapt. [Read More]

Simple Text Editor

Solutions This is a classical challenge requiring stacks. A C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <string>#include <stack>#include <iostream>#include <algorithm>using namespace std; int main() { string S, tmp; //S.reserve(1000000); int Q, op, K; cin >> Q; stack<string> states; while (Q--) { cin >> op; switch(op) { case 1: states. [Read More]
stack 

Simplify Path

Given an absolute path for a file (Unix-style), simplify it. This challenge simulates an interview problem. As you see, no more information about input constraints are provided. You - probably - have to interact with Marco (who impersonates the interviewer) and ask him some questions to refine your knowledge about the problem. Input Format Only a string is provided. The path always begins with ‘/’ (root directory). Output Format The path simplified. [Read More]
stack 

The Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element \( x \) is the first greater element on the right side of \( x \) in array. Elements for which no greater element exist, consider next greater element as \( -1 \). Input Format You are given \( N \), the number of elements, followed by \( N \) space-separated integer values. [Read More]
stack