C++实现栈逆序输出与括号匹配检测

在计算机科学中，栈是一种特殊的线性数据结构，它遵循后进先出（Last In First Out，LIFO）的原则。栈的操作主要包括压栈（push）和出栈（pop）。压栈是在栈顶添加元素，而出栈是从栈顶移除元素。栈的这些特性使得它在各种算法和程序设计中有着广泛的应用。 在C++编程语言中，可以使用数组或者链表等数据结构来实现栈。数组实现的栈具有固定大小，而链表实现的栈则可以动态地根据需要扩展容量。栈的应用非常广泛，例如在表达式求值、编译器构造、函数调用等场景中都会用到栈结构。 ### 栈的逆序输出 对于给定的字符串，可以通过将字符串中的每个字符依次压入栈中，然后再依次出栈来实现字符串的逆序输出。这种方法很简单，但是效率较高，因为它只需要遍历一次字符串即可完成逆序。 ### 括号匹配的检测 在编写或解析含有括号的表达式时，需要验证括号是否正确地匹配。使用栈可以很容易地解决这个问题。具体算法如下： 1. 遍历表达式中的每个字符。 2. 每遇到一个开括号（如'('或'['），则将其压入栈中。 3. 每遇到一个闭括号（如')'或']'），则检查栈是否为空，若为空则匹配失败；若不为空，则弹出栈顶的元素，检查这个开括号是否与当前的闭括号匹配。 4. 表达式遍历完成后，检查栈是否为空。如果为空，则括号匹配；如果不为空，则有未匹配的开括号存在，匹配失败。 ### 对数学表达式求值 对数学表达式进行求值是栈应用中的一个更高级的例子，通常涉及两个栈：一个用于数字，一个用于操作符。求值算法的大致步骤如下： 1. 从左到右扫描表达式。 2. 遇到数字时，解析完整的数字并压入数字栈。 3. 遇到操作符时，比较其与操作符栈栈顶元素的优先级： - 如果当前操作符优先级高于栈顶操作符，则将当前操作符压入栈中。 - 否则，将操作符栈顶元素弹出，从数字栈中弹出两个数字进行相应操作，然后将结果压回数字栈。之后将当前操作符压入操作符栈。 4. 遇到左括号时，直接压入操作符栈。 5. 遇到右括号时，弹出并执行操作符栈顶元素直到遇到左括号为止，弹出左括号，不执行任何操作。 6. 表达式扫描结束后，执行所有剩余的操作。 7. 数字栈顶元素即为表达式的结果。 #### 实现代码示例 以下是使用C++实现上述功能的一个简单示例代码： ```cpp #include <iostream> #include <stack> #include <string> #include <map> // 使用栈实现字符串的逆序输出 void reversePrint(const std::string& str) { std::stack<char> s; for (char c : str) { s.push(c); } while (!s.empty()) { std::cout << s.top(); s.pop(); } std::cout << std::endl; } // 检查括号是否匹配 bool checkBrackets(const std::string& str) { std::stack<char> s; for (char c : str) { switch (c) { case '(': case '[': case '{': s.push(c); break; case ')': if (s.empty() || s.top() != '(') return false; s.pop(); break; case ']': if (s.empty() || s.top() != '[') return false; s.pop(); break; case '}': if (s.empty() || s.top() != '{') return false; s.pop(); break; } } return s.empty(); } // 对数学表达式求值（简化版，不考虑多位数和多位小数） int evaluateExpression(const std::string& expr) { std::stack<int> values; std::stack<char> operators; std::map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; for (size_t i = 0; i < expr.length(); i++) { if (expr[i] == ' ') { continue; } else if (isdigit(expr[i])) { int val = 0; while (i < expr.length() && isdigit(expr[i])) { val = (val * 10) + (expr[i] - '0'); i++; } values.push(val); i--; } else if (expr[i] == '(') { operators.push(expr[i]); } else if (expr[i] == ')') { while (!operators.empty() && operators.top() != '(') { int val2 = values.top(); values.pop(); int val1 = values.top(); values.pop(); char op = operators.top(); operators.pop(); int result = 0; switch (op) { case '+': result = val1 + val2; break; case '-': result = val1 - val2; break; case '*': result = val1 * val2; break; case '/': result = val1 / val2; break; } values.push(result); } operators.pop(); } else { while (!operators.empty() && precedence[operators.top()] >= precedence[expr[i]]) { int val2 = values.top(); values.pop(); int val1 = values.top(); values.pop(); char op = operators.top(); operators.pop(); int result = 0; switch (op) { case '+': result = val1 + val2; break; case '-': result = val1 - val2; break; case '*': result = val1 * val2; break; case '/': result = val1 / val2; break; } values.push(result); } operators.push(expr[i]); } } while (!operators.empty()) { int val2 = values.top(); values.pop(); int val1 = values.top(); values.pop(); char op = operators.top(); operators.pop(); int result = 0; switch (op) { case '+': result = val1 + val2; break; case '-': result = val1 - val2; break; case '*': result = val1 * val2; break; case '/': result = val1 / val2; break; } values.push(result); } return values.top(); } int main() { std::string inputStr = "((2+3)*5)"; std::string inputExpr = "2+(3*4)-6/(1+2)"; std::cout << "逆序输出结果: "; reversePrint(inputStr); std::cout << "括号匹配结果: " << (checkBrackets(inputStr) ? "正确" : "错误") << std::endl; std::cout << "数学表达式求值结果: " << evaluateExpression(inputExpr) << std::endl; return 0; } ``` 以上代码展示了如何使用栈来逆序输出字符串、检测括号是否匹配以及求值数学表达式的基本思路。注意，这里的求值算法只是一个简化示例，它不支持多位数和多位小数的运算，同时也没有处理除数为零的情况。在实际应用中，表达式求值要复杂得多，需要考虑许多边界情况和错误处理。