C++算法: 检查表达式中三种括号的匹配

C++算法实战: 检查表达式中三种括号的匹配

本篇博客将介绍如何使用C++编写一个函数，该函数可以检查给定表达式中是否包含正确匹配的圆括号、方括号和大括号。

问题描述

假设一个表达式中允许包含三种括号：圆括号()、方括号[]和大括号{}，我们需要编写一个函数 bool check(string exp)，利用栈来判断表达式 exp 中的括号是否正确配对。如果所有括号都正确配对，则返回 true；否则返回 false。

代码实现cpp#include #include #include

bool check(std::string exp) { std::stack charStack;

// 遍历表达式中的每个字符    for (char c : exp) {        if (c == '(' || c == '[' || c == '{') {            // 如果是左括号，则入栈            charStack.push(c);        } else if (c == ')' || c == ']' || c == '}') {            // 如果是右括号，则检查栈顶是否与当前右括号匹配            if (charStack.empty()) {                return false;  // 栈为空，无法匹配            }

        char topChar = charStack.top();            charStack.pop();

        // 检查栈顶符号与当前右括号是否匹配            if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) {                return false;  // 括号不匹配            }        }    }

// 检查栈是否为空，如果不为空，则还有未匹配的左括号    return charStack.empty();}

int main() { std::string exp; std::cout << 'Enter an expression: '; std::cin >> exp;

bool isMatched = check(exp);    if (isMatched) {        std::cout << 'The parentheses are correctly matched.

'; } else { std::cout << 'The parentheses are not correctly matched. '; }

return 0;}

代码解析

1. 头文件: - <iostream>: 用于输入输出操作。 - <stack>: 用于使用栈数据结构。 - <string>: 用于字符串操作。

2. check 函数: - 接受一个 string 类型的表达式 exp 作为输入。 - 使用 std::stack<char> 创建一个字符栈 charStack。 - 遍历表达式 exp 中的每个字符 c： - 如果 c 是左括号 ('(', '[', 或 '{'), 将其压入栈中。 - 如果 c 是右括号 (')', ']', 或 '}'): - 检查栈是否为空。如果为空，则表示没有匹配的左括号，返回 false。 - 否则，弹出栈顶元素 topChar。 - 检查 topChar 是否与当前右括号 c 匹配。如果不匹配，则返回 false。 - 遍历结束后，如果栈为空，则表示所有括号都正确匹配，返回 true；否则，返回 false。

3. main 函数: - 从用户处获取表达式输入。 - 调用 check 函数检查括号是否匹配。 - 根据返回值输出相应的结果。

总结

这个算法有效地利用了栈的后进先出特性来解决括号匹配问题。通过将左括号压入栈中，并在遇到右括号时弹出栈顶元素进行匹配，我们可以轻松地判断表达式中的括号是否正确配对。