题解 | 表达式合法判断

解题思路

使用栈来解决括号匹配问题：
- 遇到左括号时入栈
- 遇到右括号时与栈顶元素匹配
- 匹配成功则出栈，失败则返回false
关键点：
- 三种括号的匹配规则
- 栈的使用
- 处理边界情况

代码

cpp
java
python

class ChkExpression {
public:
    bool chkLegal(string A) {
        stack<char> stk;
        
        for(char c : A) {
            if(c == '(' || c == '[' || c == '{') {
                stk.push(c);
            }
            else if(c == ')' || c == ']' || c == '}') {
                if(stk.empty()) return false;
                
                char top = stk.top();
                if((c == ')' && top == '(') ||
                   (c == ']' && top == '[') ||
                   (c == '}' && top == '{')) {
                    stk.pop();
                } else {
                    return false;
                }
            }
        }
        
        return stk.empty();
    }
};

import java.util.*;

public class ChkExpression {
    public boolean chkLegal(String A) {
        Stack<Character> stack = new Stack<>();
        
        for(char c : A.toCharArray()) {
            if(c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            else if(c == ')' || c == ']' || c == '}') {
                if(stack.isEmpty()) return false;
                
                char top = stack.pop();
                if((c == ')' && top != '(') ||
                   (c == ']' && top != '[') ||
                   (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

class ChkExpression:
    def chkLegal(self, A):
        stack = []
        brackets = {')': '(', ']': '[', '}': '{'} 
        for i, c in enumerate(A):
            if c in '([{':
                stack.append(c)
            elif c in ')]}':
                if not stack:
                    return False 
                top = stack.pop()
                if top != brackets[c]:
                    return False
        result = len(stack) == 0
        return result

算法及复杂度

算法：栈匹配法
时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 为字符串长度
空间复杂度： $\mathcal{O}(n)$ ，最坏情况下栈的大小