Valid Parentheses

The solution utilizes a stack data structure to validate parentheses. When encountering an opening bracket, it is pushed onto the stack. For closing brackets, the algorithm checks whether the top of the stack matches the corresponding opening bracket. If not, the input is invalid. After processing all characters, a valid expression will have an empty stack.

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            switch (ch) {
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(')
                        return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{')
                        return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[')
                        return false;
                    break;
                default:
                    stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

Remove All Adjacent Duplicates in String

This problem rqeuires removing adjacent duplicate characters iteratively. A stack is used to simulate the process. Before pushing a character, it's checked against the top of the stack. If they match, both are removed from the stack. Otherwise, the current character is added to the stack. Finally, the remaining elements in the stack are reversed to form the result string.

public class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!stack.isEmpty() && stack.peek() == ch) {
                stack.pop();
                continue;
            }
            stack.push(ch);
        }
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }
}

Evaluate Reverse Polish Notation

In this problem, numbers are pushed into a stack. When a operator is encountered, two operands are popped from the stack, applied with the operation, and the result is pushed back. It's important to maintain the correct order for subtraction and division operations.

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    int dividend = stack.pop();
                    stack.push(dividend / divisor);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}