20. Valid Parentheses

Problem Link: 20. Valid Parentheses Given a string s containing only '(', ')', '{', '}', '[', and ']', determine if the string is valid. A valid string must satisfy:

1. The left parenthesis must be closed by the same type of right parenthesis.
2. The left parenthesis must be closed in the correct order.
3. Each right parenthesis has a corresponding left parenthesis of the same type.

Overall Approach

This problem is well-known in data structures and can be solved using a stack for symmetric matching problems. It's essential to understand the different cases where parentheses may not match.

There are three types of mismatch scenarios:

1. The number of opening brackets exceeds the closing ones.
2. The brackets do not match in type.
3. The number of closing brackets exceeds the opening ones.

The code should cover these three scenarios to ensure correctness. After analysis, the implementation becomes straightforward.

Code Implementation:

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop();
        }
        return st.empty();
    }
};

1047. Remove All Adjacent Duplicates

Problem Link: 1047. Remove All Adjacent Duplicates Given a string S composed of lowercase letters, repeatedly remove adjacent duplicate characters until no more can be removed. Return the final string.

This problem is similar to the previous one, but instead of matching parentheses, it focuses on removing adjacent duplicates. A stack is used to keep track of previously seen characters.

Code Implementation:

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            } else {
                result.pop_back();
            }
        }
        return result;
    }
};

Note: This problem resembles a game where adjacent duplicates are removed, and the logic can be implemented using a stack.

150. Evaluate Reverse Polish Notation

Problem Link: 150. Evaluate Reverse Polish Notation Given an array of strings tokens representing an arithmetic expression in reverse Polish notation, compute the value of the expression.

Key Points:

• Valid operators are '+', '-', '*', and '/'.
• Each operand can be an integer or another expression.
• Division between two integers truncates toward zero.
• No division by zero.
• The input is an arithmetic expression in reverse Polish notation.
• Answers and entermediate results fit within 32-bit integers.

The problem can be solved using a stack. Each sub-expression evaluates to a result that is then used in further calculations. This is similar to the process of removing adjacent duplicates.

In this case, the evaluation follows the post-order traversal of a binary tree, where operators act as internal nodes.

The algorithm processes each token, pushing numbers onto the stack and performing operations when an operator is encountered.

The solution is efficient and leverages the stack structure for accurate computation.