利用链栈编写一个算法判断输入的表达式中的括号是否配对

算法如下：

1. 定义一个链栈，用于存储左括号。
2. 从左到右扫描表达式中的每一个字符。
3. 如果当前字符是左括号，将其入栈。
4. 如果当前字符是右括号，判断栈顶元素是否为与之匹配的左括号。
5. 如果栈顶元素不是与之匹配的左括号，说明括号不配对，返回false。
6. 如果栈顶元素是与之匹配的左括号，将其出栈。
7. 扫描完表达式后，如果栈为空，说明括号配对，返回true；否则，说明括号不配对，返回false。

代码实现：

bool isMatched(string expression) {
    stack<char> s;
    for (int i = ; i < expression.length(); i++) {
        if (expression[i] == '(') {
            s.push('(');
        } else if (expression[i] == ')') {
            if (s.empty() || s.top() != '(') {
                return false;
            }
            s.pop();
        }
    }
    return s.empty();
}

相关问题

1.利用链栈编写一个算法判断输入的表达式中的括号是否配对（假设含有左右圆括号

为了判断输入表达式中的括号是否配对，我们可以使用双端队列（Stack）数据结构，也就是链栈。链栈是一种先进后出（LIFO）的数据结构，非常适合用于处理括号匹配问题。以下是简单的步骤：

1. 初始化一个空链栈。
2. 遍历输入的表达式的每个字符：
a. 如果遇到左括号（如'('），将其压入链栈。
b. 如果遇到右括号（如')'）：
i. 如果链栈为空，说明当前右括号无对应的左括号，返回 false。
ii. 否则，弹出栈顶元素（应该是左括号）。如果它不是与当前右括号配对的左括号，也返回 false。
c. 遍历完成后，如果链栈非空，表示还有未匹配的左括号，返回 false；否则，返回 true。

下面是伪代码示例：

def is_brackets_matched(expression):
    stack = LinkedListStack()
    
    for char in expression:
        if char == '(':
            stack.push(char)
        elif char == ')':
            if stack.is_empty():
                return False
            else:
                stack.pop()  # 取消匹配

    return stack.is_empty()  # 检查剩余栈是否为空

# 示例：
expression = "((()))"
print(is_brackets_matched(expression))  # 输出：True

expression = "(()"
print(is_brackets_matched(expression))  # 输出：False

编写一个算法判断输入的表达式中括号是否配对（假设只含有左右圆括号）

编写一个算法来判断输入的表达式中括号是否配对，可以采用栈数据结构来解决这个问题。这个过程通常被称为括号匹配或平衡检查。以下是步骤：

1. 初始化一个空栈 `stack`。
2. 遍历输入表达式的每个字符：
a. 如果当前字符是左括号（如 '(', '[', '{'），将其压入栈 `stack`。
b. 如果当前字符是右括号：
- 检查栈顶元素是否与其对应：
- 对于圆括号，`('`, ')` 对应；`['`, ']` 对应；`{'`, '}' 对应。
- 若匹配，则将栈顶的左括号弹出；
- 若不匹配，说明括号不配对，返回 `false`。
3. 遍历结束后，如果栈为空，表示所有括号都已配对，返回 `true`。
4. 否则，表示还有未匹配的左括号，返回 `false`。

下面是一个伪代码示例：

def is_balanced(expression):
    stack = []
    open_brackets = {')': '(', ']': '[', '}': '{'}
    
    for char in expression:
        if char in open_brackets:
            stack.append(char)
        elif stack and stack[-1] == open_brackets[char]:
            stack.pop()
        else:
            return False
    
    return stack == []  # 判断栈是否为空

expression = "(([]))"
if is_balanced(expression):
    print("括号配对")
else:
    print("括号不配对")