ZeroJudge 解題筆記：c106. 00271 - Simply Syntax

作者：王一哲
日期：2026年3月7日


ZeroJudge 題目連結：c106. 00271 - Simply Syntax

解題想法

原文的題目連結，其中條件的部分為

The only characters in the language are the characters 'p' through 'z' and 'N', 'C', 'D', 'E', and 'I'. 句子之中只有英文小寫字母 p 到 z、大寫字母 N, C, D, E, I。
1. Every character from 'p' through 'z' is a correct sentence. 英文小寫字母 p 到 z 是合法的。
2. If s is a correct sentence, then so is Ns. 如果某個單字 s 是合法的，則 Ns 也是合法的，注意，這裡面的 s 不是專門指小寫字母 s。
3. If s and t are correct sentences, then so are Cst, Dst, Est and Ist. 如果某兩個單字 st 是合法的，則 Cst、Dst、Est 及 Ist 也是合法的，注意，這裡面的 st 不是專門指小寫字母 st。
4. Rules 0. to 3. are the only rules to determine the syntactical correctness of a sentence. 只有規則 0 到 3，沒有其它的規則。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys

def check(s):
    st = []  # 有效字元的堆疊
    for c in s[::-1]:  # 由後向前讀取
        if c in "pqrstuvwxyz":  # c 是 pqrstuvwxyz
            st.append(c)  # c 放入 st
        elif c == 'N':  # 如果 c 是 N
            if not st:  # 如果 st 是空的
                return False  # 回傳 False
            a = st.pop()  # 取出 st 最後一項
            st.append(c+a)  # c+a 加入 st
        elif c in "CDEI":  # 如果 c 是 CDEI
            if len(st) < 2:  # 如果 st 不到兩項資料
                return False  # 回傳 False
            a = st.pop()  # 取出 st 最後兩項
            b = st.pop()
            st.append(c+a+b)  # c+a+b 加入 st
        else:  # 其它狀況，c 不合法
            return False  # 回傳 False
    return len(st) == 1  # 如果 st 只有一筆資料，整個字串合法

result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    result.append("YES\n" if check(line.rstrip()) else "NO\n")
sys.stdout.write("".join(result))

也可以改成在 st 之中加入 1，代表有合法的單字，不需要真的加入單字。使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys

def check(s):
    st = []  # 有效字元的堆疊
    for c in s[::-1]:  # 由後向前讀取
        if c in "pqrstuvwxyz":  # c 是 pqrstuvwxyz
            st.append(1)  # 1 放入 st，代表有 1 個合法單字
        elif c == 'N':  # 如果 c 是 N
            if not st:  # 如果 st 是空的
                return False  # 回傳 False
            st.pop()  # 取出 st 最後一項
            st.append(1)  # 1 加入 st
        elif c in "CDEI":  # 如果 c 是 CDEI
            if len(st) < 2:  # 如果 st 不到兩項資料
                return False  # 回傳 False
            st.pop()  # 取出 st 最後兩項
            st.pop()
            st.append(1)  # 1 加入 st
        else:  # 其它狀況，c 不合法
            return False  # 回傳 False
    return len(st) == 1  # 如果 st 只有一筆資料，整個字串合法

result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    result.append("YES\n" if check(line.rstrip()) else "NO\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 324 kB，通過測試。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool check(string s) {
    stack<int> st;
    for(auto it = s.crbegin(); it != s.crend(); it++) {
        char c = *it;
        if (c >= 'p' && c <= 'z') {
            st.push(1);
        } else if (c == 'N') {
            if (st.empty()) return false;
            st.pop();
            st.push(1);
        } else if (c == 'C' || c == 'D' || c == 'E' || c == 'I') {
            if (st.size() < 2) return false;
            st.pop();
            st.pop();
            st.push(1);
        } else {
            return false;
        }
    }
    return st.size() == 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(cin >> s) cout << (check(s) ? "YES\n" : "NO\n");
    return 0;
}