C++U4-第07课-栈

【算法分析】
定义数组 s 模拟栈，TOP 为指向栈顶的指针，初始化为 0。
进行 n 次操作，if 判断是哪一种操作并执行相应的代码输出。

【参考代码】
#include <iostream>
using namespace std;

int s[110];
int TOP;

void push(int x) {
    s[++TOP] = x;
}

void pop() {
    --TOP;
}

int top() {
    return s[TOP];
}

bool empty() {
    return TOP == 0;
}

int size() {
    return TOP;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            push(x);
        }
        else if (op == "pop") {
            if (!empty()) {
                cout << "pop " << top() << endl;
                pop();
            }
            else cout << "pop fail" << endl;
        }
        else if (op == "top") {
            if (!empty()) cout << "top = " << top() << endl;
            else cout << "top fail" << endl;
        }
        else if (op == "size") {
            cout << "size = " << size() << endl;
        }
        else if (op == "empty") {
            if (!empty()) cout << "no" << endl;
            else cout << "yes" << endl;
        }
    }
    return 0;
}

【算法分析】
定义数组 s 模拟栈，TOP 为指向栈顶的指针，初始化为 0。

遍历表达式，出现(,将其入栈，出现),将与之匹配的左括号出栈。遍历结束，如果栈是空的，说明括号匹配，否则为不匹配。

【参考代码】
#include <iostream>
using namespace std;

char s[265];
int TOP;

void push(char x) {
    s[++TOP] = x;
}

void pop() {
    --TOP;
}

char top() {
    return s[TOP];
}

bool empty() {
    return TOP == 0;
}

int size() {
    return TOP;
}

int main() {
    char s;
    while (cin >> s) {
        if (s == '@')break;
        if (empty()) {
            if (s == ')') {  //判断第一个是否为) 
                cout << "NO";
                return 0;
            }
        }
        if (s == '(') push(s);
        if (s == ')') pop();
    }
    if (empty()) cout << "YES"; //栈空，匹配 
    else cout << "NO";
    return 0;
}