brackets matching in a string

Brackets matching in a string refers to the process of ensuring that all opening brackets have a corresponding closing bracket in the correct order. For example, the string "([]){}" is properly bracketed, while "([)]" is not, because the closing ")" does not match the opening "(".

There are several algorithms for checking whether a string has properly matched brackets. One common approach is to use a stack data structure, which allows you to keep track of the opening brackets as you encounter them and then check whether each closing bracket matches the most recent opening bracket. If all brackets match properly, then the stack will be empty at the end of the string.

相关问题

#include <iostream> #include <cstring> using namespace std; int main() { char a[20]; cin.getline(a, 20); long long len = strlen(a); long long sum = 0; long long xy = 0; for (int i = 0; i < len; i++) { if (a[i] == '(') { sum++; xy = 1; } if (xy == 1) { if (a[i] == ')') { sum--; } } } if (sum == 0) { cout << "yes"; } else { cout << "no"; } return 0; }给你一个由ASCII码对应字符组成的表达式，请问其中的左括号’(‘和右括号’)’是否匹配。

这段代码是用于判断一个由ASCII码对应字符组成的表达式中的左括号'('和右括号')'是否匹配。它使用一个字符数组 `a 来存储输入的表式，通过循环遍历数组，使用计数量 `sum` 来记录左括号和右括号的数量差异。如果最终 `sum` 等于0，则表示左右括号匹配，输出 "yes"；否则，表示左右括号不匹配，输出 "no"。

这段代码在逻辑上是正确的，但存在一些问题。首先，它假设输入表达式的长度不超过20个字符，并且使用了 `cin.getline()` 函数来读取包含空格的输入表达式。然而，根据题目描述，输入表达式可能会很长，并且不会包含空格。因此，建议对代码进行改进以适应更广泛的输入情况。

以下是一个改进后的代码示例：

#include <iostream>
#include <stack>

using namespace std;

bool isMatching(string expression) {
    stack<char> brackets;
    
    for (char c : expression) {
        if (c == '(') {
            brackets.push(c);
        } else if (c == ')') {
            if (brackets.empty() || brackets.top() != '(') {
                return false;
            }
            brackets.pop();
        }
    }
    
    return brackets.empty();
}

int main() {
    string expression;
    getline(cin, expression);
    
    if (isMatching(expression)) {
        cout << "yes";
    } else {
        cout << "no";
    }
    
    return 0;
}

这个改进后的代码使用了 `std::stack` 数据结构来模拟匹配过程。它通过遍历输入的字符串表达式，当遇到左括号时将其压入栈中，当遇到右括号时与栈顶元素进行匹配。如果匹配成功，则弹出栈顶元素；如果匹配失败（栈为空或栈顶元素不是左括号），则表示括号不匹配。

希望这个回答对您有所帮助！如果您有任何其他问题，请随时提问。

c++利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法 测试输入:a-{a+[x/(a-b)]}预期输出:栈空 表达式中括号匹配成功 测试输入:c*{v-y/[[x+y]}预期输出: 表达式中括号匹配失败

在C++中，我们可以使用栈的数据结构来检查括号在数学表达式中的配对情况。这个过程通常被称为括号验证（Parentheses Matching）。以下是基本思路：

1. 定义一个栈`std::stack<char>`，用于存放遇到的左括号('(', '[', '{')。
2. 遍历给定的表达式字符串，对于每个字符执行以下操作：
a. 如果是字母、数字或其他非括号字符，直接忽略。
b. 如果是左括号，将其压入栈中。
c. 如果是右括号，检查栈顶元素是否是对应的左括号（例如，'}' 和 '{'，']' 和 '[' 对应），如果匹配，则弹出栈顶元素；如果不匹配，说明括号配对错误，返回"表达式中括号匹配失败"。
3. 遍历结束后，栈为空表示所有括号都已匹配成功，否则未找到对应的右括号。

下面是简单的伪代码示例：

bool isMatching(const std::string& expression) {
    std::stack<char> brackets;
    for (char ch : expression) {
        if (ch == '(' || ch == '[' || ch == '{') {
            brackets.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (brackets.empty() || brackets.top() != ch) {
                return false; // 不匹配，返回false
            }
            brackets.pop();
        }
    }
    return brackets.empty(); // 若遍历完后栈为空，返回true，否则false
}

对于提供的测试案例：

// 测试1
if (isMatching("a-{a+[x/(a-b)]}")) {
    std::cout << "栈空" << std::endl;
} else {
    std::cout << "表达式中括号匹配失败" << std::endl;
}

// 测试2
if (isMatching("c*{v-y/[[x+y]}")) {
    std::cout << "表达式中括号匹配失败" << std::endl;
}

运行上述代码会得到相应的输出结果。