11206: 【原1206】pascal

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1206

Description

对给定一个Pascal源文件，请检查其中

(1)begin与end

(2)if,then,else

是否合法配对。

对于begin与end，可以理解为C语言中的“{”与“}”

对于if，then，else，可以这么理解：if与then合在一起相当于C语言中的if， else与C语言中的else完全相同。

注意1：为了简化问题，end出现的时候，后面没有“；”，“.”，也就是只有“end”的情况,没有“end;”,"end."。

注意2: 实际pascal语言里面是会有上述几种情况的（这只是介绍，怕这道题误导群众）。

注意3：5个关键词都会单独出现，不会有和其它字符连在一起的情况。

Example

Pascal源代码：

Var  a:char;
begin
    writeln(‘Do you fell happy ?’);
    readln(a);
    if a=’y’ then  writeln(‘smile’);
        else  writeln(‘sad’);
end

等价的C++源代码：

char a;   
int main()
{
    cout<<"Do you fell happy ?"<<endl;
    cin>>a;
    if(a=='y')
        cout<<"smile"<<endl;
    else
        cout<<"sad"<<endl;
}

Input Format

一段Pascal代码。

输入文本大小不超过4kb。

Output Format

对于一个正确匹配的Pascal代码，请输出一个"Match!"，否则输出一个"Error!"(无"")。请使用自己写的栈来完成此题。

Sample Input1

Var  a:char;
begin
    writeln(‘Do you fell happy ?’);
    readln(a);
    if a=’y’ then  writeln(‘smile’)
      else  writeln(‘sad’);
end

Sample Output1

Match!

Sample Input2

Var  a:char;
begin
    writeln(‘Do you fell happy ?’);
    readln(a);
    if a=’y’ then  writeln(‘smile’)
        else  writeln(‘sad’);

Sample Output2

Error!

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/24.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

template<typename Item>
class Stack {
    class Node {
    public:
        Item val;
        Node *next = nullptr;
    };

    int size;
    Node *top;

public:
    Stack() {
        top = nullptr;
        size = 0;
    }

    void push(const Item &item) {
        top = new Node{item, top};
    }

    Item peek() {
        return top->val;
    }

    Item pop() {
        Node *tmp = top;
        Item ret = top->val;
        top = top->next;
        delete tmp;
        return ret;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    virtual ~Stack() {
        Node *tmp;
        while (top) {
            tmp = top;
            top = top->next;
            delete tmp;
        }
    }
};

const char *tokens[] = {"begin", "end", "if", "then", "else"};

int main() {
    Stack<int> s;
    char token[100];
    bool flag = true;
    int tmp;
    while (cin >> token) {
        if (strcmp(token, "BZ") == 0) break;
        if (!flag) break;
        int i;
        for (i = 0; i < 5; ++i) {
            if (strcmp(token, tokens[i]) == 0) break;
        }
        switch (i) {
            case 0:
                s.push(0);
                break;
            case 1:
                if (s.isEmpty()) {
                    flag = false;
                    break;
                }
                while (true) {
                    tmp = s.pop();
                    if (tmp == 3) continue;
                    else if (tmp == 0) break;
                    else flag = false;
                }
                break;
            case 2:
                s.push(2);
                break;
            case 3:
                if (s.isEmpty()) {
                    flag = false;
                    break;
                }
                tmp = s.peek();
                if (tmp != 2) {
                    flag = false;
                } else {
                    s.pop();
                    s.push(3);
                }
                break;
            case 4:
                if (s.isEmpty()) {
                    flag = false;
                    break;
                }
                tmp = s.peek();
                if (tmp != 3) {
                    flag = false;
                } else {
                    s.pop();
                }
                break;
        }
    }

    if (flag && s.isEmpty()) {
        cout << "Match!" << endl;
    } else {
        cout << "Error!" << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
using namespace std;

class myList {
public:
    int data;
    myList* next = nullptr;
};

class myStack {
public:
    myList* head;

    myStack() {
        head = new myList;
    }

    void push(int b) {
        head->data = b;
        auto temp = head;
        head = new myList;
        head->next = temp;
    }

    int pop() {
        auto temp = head;
        int result = temp->next->data;
        head = head->next;
        delete temp;
        return result;
    }

    bool isEmpty() {
        return head->next == nullptr;
    }

    int getBack() {
        return head->next->data;
    }
};

int main() {
    myStack Stack;
    char op[10000][100] = { 0 };
    int num = 0;
    for (; cin >> op[num]; num++);


    //循环判断(begin 0,if then 1)
    for (int i = 0; i < num; i++) {
        if (strcmp(op[i], "begin") == 0) {
            //入栈0
            Stack.push(0);
        }
        else if (strcmp(op[i], "if") == 0) {
                Stack.push(2);
        }
        else if (strcmp(op[i], "then") == 0) {
            if (!Stack.isEmpty() && Stack.getBack() == 2) {
                Stack.pop();
                Stack.push(1);
            }
            else {
                cout << "Error!";
                return 0;
            }
        }
        else if (strcmp(op[i], "else") == 0) {
            if (!Stack.isEmpty() && Stack.getBack() == 1) {
                Stack.pop();
            }
            else {
                cout << "Error!";
                return 0;
            }
        }
        else if (strcmp(op[i], "end") == 0) {
            if (!Stack.isEmpty() && Stack.getBack() == 0) {
                Stack.pop();
                if (!Stack.isEmpty() && Stack.getBack() == 1 && strcmp(op[i + 1], "else") != 0)
                    Stack.pop();
            }
            else {
                cout << "Error!";
                return 0;
            }
        }
        else if (!Stack.isEmpty() && Stack.getBack() == 1 &&op[i][strlen(op[i])-1]==';') {
            Stack.pop();
        }
    }

    //判断是否全部弹出
    if (Stack.isEmpty())
        cout << "Match!";
    else
        cout << "Error!";

    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

template <class T>
class seqStack {
   private:
    T* data;
    int nowSize;
    int maxSize;
    void doublespace();

   public:
    seqStack(int initSize = 10);
    seqStack(const seqStack<T>&);
    ~seqStack();
    int size() const;
    void push(T);
    T top();
    T pop();
    bool isEmpty();
    T find(T) const;
    seqStack<T>& operator=(const seqStack<T>&);
    T& operator[](int);
};

template <class T>
seqStack<T>::seqStack(int initSize) {
    data = new T[initSize];
    nowSize = 0;
    maxSize = initSize;
}

template <class T>
void seqStack<T>::doublespace() {
    T* tmp;
    maxSize *= 2;
    tmp = new T[maxSize];
    for (int i = 0; i < nowSize; i++) {
        tmp[i] = data[i];
    }
    delete[] data;
    data = tmp;
    tmp = NULL;
}

template <class T>
seqStack<T>::seqStack(const seqStack<T>& right) {
    nowSize = right.nowSize;
    maxSize = right.maxSize;
    data = new T[maxSize];
    for (int i = 0; i < nowSize; i++) {
        data[i] = right.data[i];
    }
}

template <class T>
seqStack<T>::~seqStack() {
    delete[] data;
    data = NULL;
}

template <class T>
int seqStack<T>::size() const {
    return nowSize;
}

template <class T>
void seqStack<T>::push(T x) {
    if (nowSize == maxSize) {
        doublespace();
        // return;
    }
    data[nowSize++] = x;
}

template <class T>
T seqStack<T>::find(T x) const {
    for (int i = 0; i < nowSize; i++) {
        if (data[i] == x) {
            return x;
        }
    }
    return -1;
}

template <class T>
T seqStack<T>::top() {
    return data[nowSize - 1];
}

template <class T>
T seqStack<T>::pop() {
    if (nowSize != 0) {
        return data[--nowSize];
    }
    return -1;
}

template <class T>
bool seqStack<T>::isEmpty() {
    return (nowSize == 0);
}

template <class T>
seqStack<T>& seqStack<T>::operator=(const seqStack<T>& right) {
    if (this != &right) {
        delete[] data;

        nowSize = right.nowSize;
        maxSize = right.maxSize;
        data = new T[maxSize];
        for (int i = 0; i < nowSize; i++) {
            data[i] = right.data[i];
        }
    }

    return *this;
}

template <class T>
T& seqStack<T>::operator[](int x) {
    return data[nowSize - x - 1];
}

class check {
   private:
    char* data;
    int pair;
    seqStack<int> vec1;
    seqStack<int> vec2;

   public:
    check(char[]);
    ~check();
    int checkWord(char*);
    bool checkIssue(int);
    bool checkAll();
};

check::check(char words[]) : pair(0) { data = words; }

check::~check() { data = NULL; }

int check::checkWord(char* ch) {
    if (strcmp(ch, "begin") == 0) {
        return 1;
    } else if (strcmp(ch, "end") == 0) {
        return 2;
    } else if (strcmp(ch, "if") == 0) {
        return 3;
    } else if (strcmp(ch, "then") == 0) {
        return 4;
    } else if (strcmp(ch, "else") == 0) {
        return 5;
    } else {
        return 0;
    }
}

bool check::checkIssue(int i) {
    if (i == 1) {
        if (vec1.top() == 3) {
            return 0;
        } else {
            vec1.push(1);
            vec2.push(0);
        }
    } else if (i == 2) {
        if (vec1.isEmpty() || vec1.top() != 1) {
            return 0;
        } else {
            vec1.pop();
            vec2.pop();
        }
    } else if (i == 3) {
        if (vec1.top() == 3) {
            return 0;
        } else {
            vec1.push(3);
        }
    } else if (i == 4) {
        if (vec1.isEmpty() || vec1.top() != 3) {
            return 0;
        } else {
            vec1.pop();
            if (vec2.isEmpty()) {
                ++pair;
            } else {
                return 0;
            }
        }
    } else if (i == 5) {
        if (vec2.isEmpty()) {
            if (pair) {
                --pair;
            } else {
                return 0;
            }
        } else {
            if (vec2.top()) {
                int temp = vec2.pop();
                vec2.push(temp - 1);
            } else {
                return 0;
            }
        }
    }
    return 1;
}

bool check::checkAll() {
    if (data == NULL) {
        return 0;
    } else {
        char* p = data;
        char tmp[100] = {'\0'};
        int type, last = 0;
        while (1) {
            int pos = 0;
            while (*p == ' ') {
                p++;
            }
            while (*p && *p != ' ') {
                tmp[pos++] = *p;
                p++;
            }
            tmp[pos++] = 0;
            type = checkWord(tmp);
            checkIssue(type);
            if (*p == 0) {
                break;
            }
        }
        while (vec1.isEmpty() == 0) {
            int tmp = vec1.pop();
            if (tmp == 1) {
                return 0;
            } else if (tmp == 3 && last != 4) {
                return 0;
            }
            last = type;
        }
        return 1;
    }
}

int main() {
    int pair, pos = 0;
    bool flag = 1;
    char words[50000], ch;

    ch = getchar();
    while (ch != EOF) {
        if (ch == '\n') {
            ch = ' ';
        }
        words[pos++] = ch;
        ch = getchar();
    }
    words[pos] = 0;

    check che(words);
    if (che.checkAll()) {
        cout << "Match!" << endl;
    } else {
        cout << "Error!" << endl;
    }

    return 0;
}

skyzh's solution

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

enum program { BEGIN = 0, END, IF, THEN, ELSE };

template <typename T>
class Stack {
public:
    T *data;
    int top_ptr;
    Stack(int cap) : data(new T[cap]), top_ptr(0) {}
    ~Stack() { delete[] data; }
    void push(const T& d) { data[top_ptr++] = d; }
    T pop() { return data[--top_ptr]; }
    T top() { return data[top_ptr - 1]; }
    bool empty() { return top_ptr == 0; }
};

void pop_else_then(Stack<int> &d) {
    while (!d.empty()) {
        if (d.top() == THEN) d.pop();
        else if (d.top() == ELSE) d.pop();
        else return;
    }
}

void pop_then(Stack<int> &d) {
    while (!d.empty()) {
        if (d.top() == THEN) d.pop();
        else return;
    }
}

bool run() {
    Stack <int> d(10000);
    char token[100];
    while (cin >> token) {
        if (strcmp(token, "begin") == 0) {
            d.push(BEGIN);
        }
        if (strcmp(token, "end") == 0) {
            if (d.empty()) return false;
            if (d.top() == BEGIN) d.pop(); else {
                pop_else_then(d);
                if (d.empty()) return false;
                if (d.top() == BEGIN) d.pop(); else return false;
            }
        }
        if (strcmp(token, "if") == 0) {
            d.push(IF);
        }
        if (strcmp(token, "else") == 0) {
            if (d.empty()) return false;
            if (d.top() == THEN) { d.pop(); d.push(ELSE); } else {
                pop_then(d);
                if (d.empty()) return false;
                if (d.top() == THEN) d.pop(); else return false;
            }
        }
        if (strcmp(token, "then") == 0) {
            if (d.empty()) return false;
            if (d.top() == IF) { d.pop(); d.push(THEN); } else return false;
        }
    }
    pop_else_then(d);
    return d.empty();
}
int main() {
    if (run()) cout << "Match!" << endl; else cout << "Error!" << endl;
    return 0;
}

yyong119's solution

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

class stack {
private:
    char *data;
    int topP, maxSize;

    void doubleSpace() {
        char *tmp = data;
        data = new char[maxSize * 2];
        for (int i = 0; i < maxSize; ++i)data[i] = tmp[i];
        maxSize *= 2;
        delete[] tmp;
    }
public:
    stack() :topP(-1), maxSize(10) {
        data = new char[maxSize];
    }
    bool empty() {
        return topP == -1;
    }
    void push(char c) {
        if (topP == maxSize - 1)doubleSpace();
        data[++topP] = c;
    }
    char pop() {
        if (!empty()) return data[topP--];
    }
    char top() {
        if (!empty()) return data[topP];
    }
};

int main() {

    ios::sync_with_stdio(false);
    stack v;
    char str[1000];
    bool isOk = true;
    while (cin >> str) {
        if (strcmp(str, "begin") == 0 || strcmp(str, "if") == 0)
            v.push(str[0]);
        else if (strcmp(str, "then") == 0) {
            if (v.empty() || v.pop() != 'i') isOk = false;
            else v.push('t');
        }
        else if (strcmp(str, "end") == 0) {
            do {
                if (v.empty() || v.top() == 'i') {
                    isOk = false; break;
                }
                if (v.pop() == 'b')break;
            } while (true);
            if (!isOk)break;
        }
        else if (strcmp(str, "else") == 0) {
            if (v.empty() || v.pop() != 't') isOk = false;
        }
        if (!isOk) break;
    }
    while (isOk && !v.empty()) {
        if (v.pop() != 't') isOk = false;
    }
    if (isOk) cout << "Match!" << '\n';
    else cout << "Error!" << '\n';
    return 0;
}