动态堆栈类及括号匹配(考察类的构建与应用)

本文主要是介绍动态堆栈类及括号匹配(考察类的构建与应用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

NWAFU OOP02_02

一、题目描述

Description

设计一个动态字符堆栈类，要求堆栈可存储的字符数量可动态扩展，在构造函数中使用new进行初始堆栈空间内存分配，在析构函数中采用delete释放内存，堆栈类框架如下所示：

class CStack
{char *s;int tp;int size;public:CStack(int initSize = 5);~CStack();bool isEmpty();bool isFull();void push(char c);char pop();char top();};

编码完善上述动态字符堆栈类，基于此堆栈类，判断一个字符串中的括号是否正确匹配。如输入"{[(1+2)/(3+4)*5-3]*2}/3-4"，则字符串中的括号匹配，若输入"[(])"，则字符串中的括号不匹配。

Input

采用getline(cin, string)读入一个可能包含"()[]{}"三种括号的字符串。

Output

判断输入字符串中的括号是否正确匹配，若正确匹配，输出"Balanced"，否则输出"Not balanced"。

Sample Input 1

{[9+(3-1)*3+10]-5}/2

Sample Output 1

Balanced

Sample Input 2

int main(){int a;cin >> a; if (a==0)cout << "Hello world!" << endl;else cout << "Hello China!" << endl;

Sample Output 2

Not balanced

二、设计步骤

代码实现：

#include <iostream>
#include <string>
using namespace std;class CStack {char *s;int tp;int size;public:CStack(int initSize = 5);~CStack();bool isEmpty();bool isFull();void push(char c);char pop();char top();
};CStack::CStack(int initSize) {size = initSize;s = new char[size];tp = -1;
}CStack::~CStack() {delete[] s;
}bool CStack::isEmpty() {return (tp == -1);
}bool CStack::isFull() {return (tp == size - 1);
}void CStack::push(char c) {if (isFull()) {int newSize = size * 2;char *newS = new char[newSize];for (int i = 0; i < size; ++i) {newS[i] = s[i];}delete[] s;s = newS;size = newSize;}s[++tp] = c;
}char CStack::pop() {if (isEmpty()) {return '\0'; }return s[tp--];
}char CStack::top() {if (isEmpty()) {return '\0'; }return s[tp];
}bool isMatchingPair(char character1, char character2) {if (character1 == '(' && character2 == ')')return true;else if (character1 == '[' && character2 == ']')return true;else if (character1 == '{' && character2 == '}')return true;elsereturn false;
}bool isBalanced(string exp) {CStack stack(exp.length());for (int i = 0; i < exp.length(); i++) {if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{')stack.push(exp[i]);else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {if (stack.isEmpty() || !isMatchingPair(stack.pop(), exp[i]))return false;}}return stack.isEmpty();
}int main() {string expression;getline(cin, expression);if (isBalanced(expression))cout << "Balanced";elsecout << "Not balanced";return 0;
}