设计一个算法判断输入的表达式中括号(圆括号、方括号、大括号)是否配对

设计这样一个算法来判断输入的表达式中括号是否配对，可以采用栈数据结构，因为括号的匹配规则就是“左开右闭”原则，类似于递归下降解析。以下是基本步骤：

1. 初始化一个空栈 `stack`。

2. 遍历输入的表达式的每个字符，依次检查每个字符：
- 如果遇到 '(', '[' 或 '{'（左括号），将其压入栈顶。
- 如果遇到 ')'，']', 或 '}'（右括号），先检查栈顶元素是否是对应的左括号：
- 如果不是，说明配对不成立，返回 False。
- 否则，弹出栈顶元素。

3. 遍历完成后，如果栈为空，说明所有括号都已成对出现，返回 True；否则，表示还有未关闭的括号，返回 False。

以下是伪代码形式：

function is_balanced(expression):
    stack = []
    
    for char in expression:
        if char in ['(', '[', '{']:
            stack.append(char)
        elif char in [')', ']', '}']:
            if not stack or stack.pop() != char:
                return False
    
    return stack.isEmpty()

相关问题

设计一个算法判断输入的表达式中括号(圆括号、方括号、大括号）是否配对

设计这样一个算法通常可以采用栈数据结构来辅助解决。步骤如下：

1. 创建一个空栈 `stack`。

2. 遍历输入表达式的每个字符：
a. 如果遇到左括号 ( 或 [ 或 {)，将其压入栈中。
b. 如果遇到右括号 )、] 或 }：
i. 检查栈顶元素是否与其相匹配。例如，')' 对应 '(', ']' 对应 '[', '}' 对应 '{'。
ii. 匹配成功则弹出栈顶元素；如果不匹配，则返回错误，因为括号不配对。
c. 如果遍历结束，而栈非空，说明还有未关闭的左括号，返回错误。

3. 遍历结束后，如果栈为空，说明所有括号都已配对，返回 true；否则返回 false。

下面是伪代码形式：

def is_balanced(expression):
    stack = []
    pairs = {"(": ")", "[": "]", "{": "}"}
    
    for char in expression:
        if char in pairs:
            stack.append(char)
        elif not stack or stack[-1] != pairs[char]:
            return False
            
    return not stack

假设表达式中允许包含圆括号、方括号和大括号3中括号，编写一个算法判断表达式中括号是否正确配对。

这个问题可以使用栈来解决。具体步骤如下：
1. 创建一个空栈。
2. 从左到右遍历表达式中的每个字符。
3. 如果当前字符是左括号，则将其压入栈中。
4. 如果当前字符是右括号，则弹出栈顶元素并判断是否与当前字符匹配。如果不匹配，则表达式中的括号不正确配对，返回false。
5. 如果遍历完整个表达式后栈为空，则表达式中的括号正确配对，返回true；否则，表达式中的括号不正确配对，返回false。

C++代码实现如下：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

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

int main() {
    string expr;
    cout << "请输入一个包含圆括号、方括号和大括号的表达式：" << endl;
    cin >> expr;
    if (isMatching(expr)) {
        cout << "括号正确配对！" << endl;
    } else {
        cout << "括号不正确配对！" << endl;
    }
    return 0;
}