Stack¶
Table of Contents¶
- 20. Valid Parentheses (Easy)
- 71. Simplify Path (Medium)
- 155. Min Stack (Medium)
- 150. Evaluate Reverse Polish Notation (Medium)
- 224. Basic Calculator (Hard)
20. Valid Parentheses¶
# Stack
def is_valid(s: str) -> bool:
if len(s) % 2:
return False
pairs = {
"(": ")",
"{": "}",
"[": "]",
}
stack = []
for ch in s:
if ch in pairs:
stack.append(ch)
elif not stack or ch != pairs[stack.pop()]:
return False
return True if not stack else False
def test_is_valid():
assert is_valid("()[]{}")
assert not is_valid("(]")
assert not is_valid("([)]")
assert is_valid("{[]}")
#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
stack<char> stack;
if (s.length() % 2 == 1) return false;
for (char& ch : s) {
if (stack.empty() || map.find(ch) == map.end()) {
stack.push(ch);
} else {
if (map[ch] != stack.top()) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
};
int main() {
Solution s;
assert(s.isValid("()") == true);
assert(s.isValid("()[]{}") == true);
assert(s.isValid("(]") == false);
assert(s.isValid("([)]") == false);
assert(s.isValid("{[]}") == true);
return 0;
}
71. Simplify Path¶
def simplify_path_stack(path: str) -> str:
if not path:
return "/"
stack = []
for p in path.split("/"):
if p == "" or p == ".":
continue
if p != "..":
stack.append(p)
elif stack:
stack.pop()
return "/" + "/".join(stack)
def test_simplify_path_stack():
assert simplify_path_stack("/home/") == "/home"
assert simplify_path_stack("/../") == "/"
assert simplify_path_stack("/home//foo/") == "/home/foo"
assert simplify_path_stack("/a/./b/../../c/") == "/c"
155. Min Stack¶
"""
- Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.
"""
# Stack
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
if self.stack:
self.stack.append((val, min(val, self.getMin())))
else:
self.stack.append((val, val))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
obj = MinStack()
obj.push(3)
obj.push(2)
obj.pop()
print(obj.top()) # 3
print(obj.getMin()) # 3
#include <algorithm>
#include <climits>
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
class MinStack {
stack<pair<int, int>> st;
public:
MinStack() { st.emplace(0, INT_MAX); }
void push(int val) { st.emplace(val, min(getMin(), val)); }
void pop() { st.pop(); }
int top() { return st.top().first; }
int getMin() { return st.top().second; }
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
cout << minStack.getMin() << endl; // -3
minStack.pop();
cout << minStack.top() << endl; // 0
cout << minStack.getMin() << endl; // -2
return 0;
}
150. Evaluate Reverse Polish Notation¶
from typing import List
# Stack
def evalRPN(tokens: List[str]) -> int:
stack = []
for c in tokens:
if c == "+":
stack.append(stack.pop() + stack.pop())
elif c == "-":
a, b = stack.pop(), stack.pop()
stack.append(b - a)
elif c == "*":
stack.append(stack.pop() * stack.pop())
elif c == "/":
a, b = stack.pop(), stack.pop()
stack.append(int(b / a))
else:
stack.append(int(c))
return stack[0]
def test_evalRPN():
print(evalRPN(["2", "1", "+", "3", "*"])) # 9
print(evalRPN(["4", "13", "5", "/", "-"])) # 2
print(evalRPN(["18"])) # 18
print(evalRPN(["4", "3", "-"])) # 1
224. Basic Calculator¶
# Stack
def calculate(s: str) -> int:
stack = []
result = 0
number = 0
sign = 1
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "+":
result += sign * number
number = 0
sign = 1
elif char == "-":
result += sign * number
number = 0
sign = -1
elif char == "(":
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ")":
result += sign * number
number = 0
result *= stack.pop() # pop sign
result += stack.pop() # pop previous result
result += sign * number
return result
print(calculate("(1+(4+5+2)-3)+(6+8)")) # 23