Stack
Ex 2:
You are keeping score for a basketball game with some new rules. The game consists of
several rounds, where the scores of past rounds may affect future rounds' scores.
At the beginning of the game, you start with an empty record. You are given a list of
strings ops, where ops[i] is the operation you must apply to the record, with the
following rules:
A non-negative integer x (from 0 to 9) - record a new score of x
'+' - Record a new score that is the sum of the previous two scores. It is
guaranteed there will always be two previous scores.
'D' - Record a new score that is double the previous score. It is guaranteed there
will always be a previous score.
'C' - Invalidate the previous score, removing it from the record. It is guaranteed
there will always be a previous score.
Finally, return the sum of all scores in the record.
For example:
ops = "52CD+"
'5' - add to the record. Record now is [5]
'2' - add to the record. Record now is [5,2]
'C' - invalid the previous score (2). Record now is [5]
'D' - Record new score that is double of previous score (5*2). Record now
is [5,10]
'+' - Record a new score that is the sum of the previous two scores. Record now
is [5,10,15]
Return the sum: 5+10+15 = 30
int baseballScore(string ops){
/*TODO*/
stack<int> record;
int n = [Link]();
for (int i = 0; i < n; i++) {
if (isdigit(ops[i])) {
int val = ops[i] - '0';
[Link](val);
}
else if (ops[i] == 'D') {
int previousScore = [Link]();
[Link](previousScore * 2);
}
else if (ops[i] == 'C') {
[Link]();
}
else if (ops[i] == '+') {
int first = [Link]();
[Link]();
int second = [Link]();
[Link](first);
[Link](first + second);
}
}
int sum = 0;
while ([Link]() > 0) {
sum += [Link]();
[Link]();
}
return sum;
}
Ex 3:
Given an array nums[] of size N having distinct elements, the task is to find the
next greater element for each element of the array
Next greater element of an element in the array is the nearest element on the
right which is greater than the current element.
If there does not exist a next greater of a element, the next greater element for
it is -1
Note: iostream, stack and vector are already included
Example 1:
Input:
nums = {15, 2, 4, 10}
Output:
{-1, 4, 10, -1}
// iostream, stack and vector are included
vector<int> nextGreater(vector<int>& arr){
int n = [Link]();
vector<int> resultVector(n);
stack<int> potentialGreater;
for (int i = n - 1; i >= 0; i--) {
int val = arr[i];
while (![Link]() && [Link]() <= val) {
[Link]();
}
if ([Link]()) {
resultVector[i] = -1;
}
else {
resultVector[i] = [Link]();
}
[Link](val);
}
return resultVector;
}
Ex 4:
Given a string S of characters, a duplicate removal consists of choosing two
adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made.
Included libraries: vector, list, stack
string removeDuplicates(string S){
/*TODO*/
string result;
for (char c : S) {
if ([Link]() || [Link]() != c) {
result.push_back(c);
}
else {
result.pop_back();
}
}
return result;
}
Ex 5:
Given a string s containing just the characters '(', ')', '[', ']', '{', and '}'. Check
if the input string is valid based on following rules:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
For example:
String "[]()" is a valid string, also "[()]".
String "[])" is not a valid string.
Your task is to implement the function
bool isValidParentheses (string s){
/*TODO*/
}
bool isValidParentheses (string s){
/*TODO*/
stack<char> check;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
[Link](c);
}
else if (c == ')') {
if (![Link]() && [Link]() == '(') {
[Link]();
}
else {
return false;
}
}
else if (c == ']') {
if (![Link]() && [Link]() == '[') {
[Link]();
}
else {
return false;
}
}
else if (c == '}') {
if (![Link]() && [Link]() == '{') {
[Link]();
}
else {
return false;
}
}
}
return [Link]();
}
Ex 6:
A Maze is given as 5*5 binary matrix of blocks and there is a rat initially at the
upper left most block i.e., maze[0][0] and the rat wants to eat food which is
present at some given block in the maze (fx, fy). In a maze matrix, 0 means that
the block is a dead end and 1 means that the block can be used in the path from
source to destination. The rat can move in any direction (not diagonally) to any
block provided the block is not a dead end.
Your task is to implement a function with following prototype to check if there
exists any path so that the rat can reach the food or not:
bool canEatFood(int maze[5][5], int fx, int fy);
Template:
#include <iostream> #include <fstream> #include <string> #include
<cstring> #include <stack> #include <vector> using namespace std;
class Node { public: int x, y; int dir; node(int i, int j) { x = i; y = j; //
Initially direction // set to 0 dir = 0; } };
Some suggestions: - X : x coordinate of the node - Y : y coordinate of the
node - dir : This variable will be used to tell which all directions we have tried
and which to choose next. We will try all the directions in anti-clockwise manner
starting from up.
If dir=0 try up direction.
If dir=1 try left direction.
If dir=2 try down direction.
If dir=3 try right direction.
bool canEatFood(int maze[5][5], int fx, int fy){
/*TODO*/
int visited[5][5] = {0};
stack<Node> pathSearch;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
[Link](Node(0, 0));
visited[0][0] = 1;
while (![Link]()) {
Node current = [Link]();
[Link]();
if (current.x == fx && current.y == fy) return true;
if ([Link] < 4) {
int nx = current.x + dx[[Link]];
int ny = current.y + dy[[Link]];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && maze[nx][ny] == 1 && !visited[nx]
[ny]) {
visited[nx][ny] = 1;
[Link](Node(nx, ny));
}
[Link]++;
[Link](current);
}
}
return false;
}
Ex 7:
Bài toán stock span là một bài toán về chủ đề kinh tế tài chính, trong đó ta có
thông tin về giá của một cổ phiếu qua từng ngày. Mục tiêu của bài toán là
tính span của giá cổ phiếu ở từng ngày.
Span của giá cổ phiếu tại ngày thứ i (ký hiệu là Si) được định nghĩa là số ngày liên
tục nhiều nhất liền trước ngày thứ i có giá cổ phiếu thấp hơn, cộng cho 1 (cho
chính nó).
Ví dụ, với chuỗi giá cổ phiếu là [100, 80, 60, 70, 60, 75, 85].
1. Ngày thứ 0 không có ngày liền trước nên S0 bằng 1.
2. Ngày thứ 1 có giá nhỏ hơn giá ngày thứ 0 nên S1 bằng 1.
3. Ngày thứ 2 có giá nhỏ hơn giá ngày thứ 1 nên S2 bằng 1.
4. Ngày thứ 3 có giá lớn hơn giá ngày thứ 2 nên S3 bằng 2.
5. Ngày thứ 4 có giá nhỏ hơn giá ngày thứ 3 nên S4 bằng 1.
6. Ngày thứ 5 có giá lớn hơn giá ngày thứ 4, 3, 2 nên S5 bằng 4.
7. Ngày thứ 6 có giá lớn hơn giá ngày thứ 5, 4, 3, 2, 1 nên S6 bằng 6.
Kết quả sẽ là [1, 1, 1, 2, 1, 4, 6].
vector<int> stock_span(const vector<int>& ns) {
// STUDENT ANSWER
int n = [Link]();
vector<int> result(n);
stack<int> s;
for (int i = 0; i < n; i++) {
int val = ns[i];
while (![Link]() && ns[[Link]()] < val) {
[Link]();
}
if ([Link]()) {
result[i] = i + 1;
}
else {
result[i] = i - [Link]();
}
[Link](i);
}
return result;
}
Ex 8:
Given string S representing a postfix expression, the task is to evaluate the expression and find
the final value. Operators will only include the basic arithmetic operators like *, /, + and -.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., when a pair of
operands is followed by an operator.
For example: Given string S is "2 3 1 * + 9 -". If the expression is converted into an infix
expression, it will be 2 + (3 * 1) – 9 = 5 – 9 = -4.
Requirement: Write the function to evaluate the value of postfix expression.
int evaluatePostfix(string expr){
/*TODO*/
stack<int> s;
string number;
for (char c : expr) {
if (isdigit(c)) {
number += c;
else if (c == ' ') {
if (number != "") {
[Link](stoi(number));
number = "";
else {
int first = [Link]();
[Link]();
int second = [Link]();
[Link]();
if (c == '*') {
[Link](first * second);
else if (c == '+') {
[Link](first + second);
}
else if (c == '/') {
[Link](second / first);
else if (c == '-') {
[Link](second - first);
return [Link]();
}