题目描述:
用顺序存储实现栈的初始化、入栈、出栈、取栈顶、判栈空操作。调用以上操作实现判断从键盘输入的括号序列是否匹配。
输入:
括号序列#(#为括号输入结束符号)
输出:
匹配或不匹配
样例输入:{[()]}#
样例输出:匹配
基本思路:
这是一个较为简单的栈的运用。我们首先要遍历整个括号序列。当所在的元素为左括号时,便把其压入栈中。当我们遇到右括号时,便将其与栈顶的元素进行比较。如果能够匹配,则将栈顶的元素弹出,继续进行括号序列的遍历。如果不匹配,则说明此括号序列的括号不匹配,程序结束。
#include#include using namespace std; class Stack {//自定义栈 public: int top;//栈顶元素的下标 int maxSize;//自定义栈的最大容量 char* data;//存放数据的数组 public: Stack(int sz=100) {//构造函数 maxSize = sz; data = new char[maxSize]; top = 0; } bool EnStack(char& x) { if (top == maxSize - 1) { cout << "error! overflow" << endl; return false; } data[top] = x; top++; return true; } bool DeStack() { if (top == 0) { return false; } top--; return true; } char getTop() { if (top == 0) { return '!'; } return data[top-1]; } bool IsEmpty() { if (top == 0) return true; else return false; } }; int main() { Stack s; string str; cin >> str; int i = 0; int flag = 1;//用于检测 }}# 类的情况 for (; i < str.length(); i++) { if (str[i] == '#') break; else if (str[i] == '{' || str[i] == '[' || str[i] == '(') { s.EnStack(str[i]); } else if (str[i] == ')') { flag = 0; if (s.getTop() == '(') s.DeStack(); else { cout << "不匹配" << endl; return 0; } } else if (str[i] == ']') { flag = 0; if (s.getTop() == '[') s.DeStack(); else { cout << "不匹配" << endl; return 0; } } else if (str[i] == '}') { flag = 0; if (s.getTop() == '{') s.DeStack(); else { cout << "不匹配" << endl; return 0; } } } if (flag || !s.IsEmpty()) cout << "不匹配" << endl; else cout << "匹配" << endl; return 0; }
有问题,欢迎交流指正



