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

前言

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;
    else
        return 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";
    else
        cout << "Not balanced";
    return 0;
}

总结

EOF