11028: 【原1028】语句匹配

题目

题目描述

author: zyz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1028

Description

Pascal语言中，复合语句用begin...end表示，条件语句用if...then...else...表示，其中，else子句可以出现也可以不出现。现在提取出一些语句中的所有begin、end、if、then、else，编写一个程序检查它们能否匹配，以构成若干条合法的语句。

Input Format

输入包含两行。

第1行：一个整数N，表示接下来有N个字符串将读入。

第2行：包含N个字符串，每个字符串一定是{"begin","end","if","then","else"}之一（不包括引号）。这些字符串表示从一系列语句中依次提取出的所有元素。

Output Format

若输入可以构成若干条合法语句，输出一行"YES"，否则输出一行"NO"。（不包含引号）

Sample Input

9
if then begin if then begin end end else

Sample Output

YES

Sample Input

4
if begin end then

Sample Output

NO

说明

\( N \leq 100 \)

注意begin...end不能作为判断条件。（见样例2）

注意then与else之后都允许出现不止一条if语句或复合语句。

感谢聂步青提供加强数据。

FineArtz's solution

/* 语句匹配 */
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
    int n;
    cin >> n;
    stack<string> state;
    while(n--){
        string s;
        cin >> s;
        if (state.empty()){
            if (s == "then" || s == "end" || s == "else"){
                cout << "NO" << endl;
                return 0;
            }
            state.push(s);
            continue;
        }
        string t = state.top();
        if (s == "then"){
            if (t != "if"){
                cout << "NO" << endl;
                return 0;
            }
            else{
                state.pop();
                state.push(s);
            }
        }
        else if (s == "else"){
            if (t == "begin" || t == "if"){
                cout << "NO" << endl;
                return 0;
            }
            while (!state.empty() && state.top() != "then")
                state.pop();
            if (state.empty()){
                cout << "NO" << endl;
                return 0;
            }
            state.pop();
        }
        else if (s == "end"){
            if (t == "if"){
                cout << "NO" << endl;
                return 0;
            }
            while (!state.empty() && state.top() != "begin")
                state.pop();
            if (state.empty()){
                cout << "NO" << endl;
                return 0;
            }
            state.pop();
        }
        else if (s == "begin"){
            if (t == "if"){
                cout << "NO" << endl;
                return 0;
            }
            state.push(s);
        }
        else if (s == "if"){
            if (t == "if"){
                cout << "NO" << endl;
                return 0;
            }
            state.push(s);
        }
    }
    while (!state.empty() && state.top() == "then") state.pop();
    if (!state.empty()) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

ligongzzz's solution

//WA - 90

#include <iostream>
#include <cstring>
using namespace std;

int bucket[5] = { 0 };

int cmp(char arr[]) {
    if (!strcmp(arr, "begin"))
        return 0;
    if (!strcmp(arr, "end"))
        return 1;
    if (!strcmp(arr, "if"))
        return 2;
    if (!strcmp(arr, "then"))
        return 3;
    if (!strcmp(arr, "else"))
        return 4;
}

int main() {
    int n;
    cin >> n;
    bool flag = false, isif = false, isbegin = false;
    char arr[109][6];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        bucket[cmp(arr[i])]++;
        if (cmp(arr[i]) == 2)
            isif = true;
        if (cmp(arr[i]) == 3 && isif == true) 
            isif = false;
        if (cmp(arr[i]) == 0 && isif == true) 
            isbegin = true;
        if (cmp(arr[i]) == 1 && isif == true && isbegin == true) {
            cout << "NO";
            flag = true;
            break;
        }
        if (bucket[0] < bucket[1] || bucket[2] < bucket[3] || bucket[2] < bucket[4]) {
            cout << "NO";
            flag = true;
            break;
        }
    }
    if (flag == false) {
        if (bucket[0] == bucket[1] && bucket[2] == bucket[3]) {
            cout << "YES";
        }
        else {
            cout << "NO";
        }
    }
    return 0;
}