Bài 1
int baseballScore(string ops){
stack<int> record; // Stack to store the scores
for (char op : ops) {
if (op == '+') {
int prev1 = record.top();
record.pop();
int prev2 = record.top();
int score = prev1 + prev2;
record.push(prev1);
record.push(score);
} else if (op == 'D') {
int prev = record.top();
int score = prev * 2;
record.push(score);
} else if (op == 'C') {
record.pop();
} else {
int score = op - '0';
record.push(score);
}
}
int sum = 0;
while (!record.empty()) {
sum += record.top();
record.pop();
}
return sum;
}
Bài 2
void push(T item) {
list.add(item);
}
T pop() {
T topItem = list.get(list.size() - 1);
list.removeAt(list.size() - 1);
return topItem;
}
T top() {
return list.get(list.size() - 1);
}
bool empty() {
return list.empty();
}
int size() {
return list.size();
}
void clear() {
list.clear();
}
Bài 3
vector<int> nextGreater(const vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && nums[stk.top()] < nums[i]) {
result[stk.top()] = nums[i];
stk.pop();
}
stk.push(i);
}
return result;
}
Bài 4
int evaluatePostfix(string expression){
stack<int> operandStack;
istringstream iss(expression);
string token;
while (iss >> token) {
// Check if the token is an operator
if (token == "+" || token == "-" || token == "*" || token == "/") {
int operand2 = operandStack.top();
operandStack.pop();
int operand1 = operandStack.top();
operandStack.pop();
int result;
if (token == "+")
result = operand1 + operand2;
else if (token == "-")
result = operand1 - operand2;
else if (token == "*")
result = operand1 * operand2;
else if (token == "/")
result = operand1 / operand2;
operandStack.push(result);
} else {
int operand = stoi(token);
operandStack.push(operand);
}
}
return operandStack.top();
}
Bài 5
bool canEatFood(int maze[5][5], int fx, int fy){
stack<node> pathStack;
vector<vector<bool>> visited(5, vector<bool>(5, false));
// Starting node: (0, 0)
node start(0, 0);
pathStack.push(start);
while (!pathStack.empty()) {
node current = pathStack.top();
pathStack.pop();
int x = current.x;
int y = current.y;
int dir = current.dir;
visited[x][y] = true;
if (x == fx && y == fy)
return true;
while (dir < 4) {
int newX = x, newY = y;
// Move in the chosen direction
if (dir == 0) // Up
newX--;
else if (dir == 1) // Left
newY--;
else if (dir == 2) // Down
newX++;
else if (dir == 3) // Right
newY++;
if (newX >= 0 && newX < 5 && newY >= 0 && newY < 5 && maze[newX][newY]
== 1 && !visited[newX][newY]) {
node next(newX, newY);
next.dir = 0; // Reset direction for the new node
pathStack.push(next);
current.dir = dir + 1;
pathStack.push(current);
break;
}
dir++;
}
}
// No path to the food exists
return false;
}
Bài 6
string removeDuplicates(string S){
stack<char> charStack;
for (char ch : S) {
if (!charStack.empty() && charStack.top() == ch) {
charStack.pop();
} else {
charStack.push(ch);
}
}
string result;
while (!charStack.empty()) {
result = charStack.top() + result;
charStack.pop();
}
return result;
}
Bài 7
vector<int> stock_span(const vector<int> &ns) {
vector<int> spans;
stack<pair<int, int>> stk;
if (ns.empty()) return spans;
for (size_t i = 0; i < ns.size(); i++) {
int span = 1;
while (!stk.empty() && stk.top().second <= ns[i]) {
span += stk.top().first;
stk.pop();
}
spans.push_back(span);
stk.push({ span, ns[i] });
}
return spans;
}
Bài 8
bool isValidParentheses (string s){
stack<char> parenthesesStack;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
parenthesesStack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (parenthesesStack.empty()) {
return false;
}
char top = parenthesesStack.top();
parenthesesStack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}'
&& top != '{')) {
return false;
}
}
}
return parenthesesStack.empty();
