逆ポーランド記法への書き換え#1 CoffeeScript(Beta)編（paizaランク B 相当）

字句解析済みの数式 S の n 個の字句とその字句の種類 (a₁, t₁) 〜 (a_n, t_n) が中置記法の順で文字列で与えられます。

(a₁, t₁) 〜 (a_n, t_n) を後置記法(逆ポーランド記法)に書き換えて n 行で出力してください。

数式は以下のEBNFに従います。

EBNF

<expr>   ::= <number> ( '+' <number> )* 
<number> ::= [0-9]+ 

※ただし、 0 を除いて整数の先頭に 0 がある数字はないものとします。

例）000、001、023

EBNFについて

EBNFとはBNFと正規表現の組み合わせによって記述される文法で、言語の構文を定義するために用いられます。

BNFの記法について

EBNFは非終端記号と終端記号を用いた生成規則によって記述されます。

・ 非終端記号とは

角括弧で囲まれた記号で表されたもので、ある規則で定義されるシンボルとなります。

・ 終端記号とは

実際に使用される数字、文字、文字列です。

BNFの場合は引用符 ("") によって囲まれます。

記述例は以下の通りです。

<paiza> ::= <string>; 
<string> ::= <char> | <string> <char>; 
<char> ::= "p" | "a" | "i" | "z"; 

左辺のシンボルは右辺によって定義されます。

正規表現について

正規表現は文字列の集合(パターン)を表す汎用的な記法です。メタ文字が定義され、その組み合わせによって文字列の部分的なマッチングを検索することができます。

メタ文字の例

・ '*'

直前の文字が 0 回以上繰り返される文字列にマッチ

・ '+'

直前の文字が 1 回以上繰り返される文字列にマッチ

・ '|'

前後の文字列の論理和を取る文字列にマッチ

・ '( )'

'('と')'の中の文字列をグループとして扱う

・ '[ ]'

'['と']'の中の文字列のいずれかにマッチ

今回の場合、式 <expr> は 1 つの <number> と 0 個以上の ( '+' <number> ) の組み合わせで構成されていることを表しています。

また、<number> は 0 から 9 のいずれかの文字が 1 つ以上連続で繋がったものです。

中置記法について

中置記法は、演算子を操作対象の間に記述する方法です。

例1）1+2は 1 に 2 を足すことを意味します。

例2）123*456-789は 123 に 456 を掛けた結果から 789 を引くことを意味します。

後置記法について

後置記法は、演算子を操作対象の後ろに記述する方法です。

例1）1 2 + は 1 に 2 を足すことを意味します。

例2）123 456 * 789 - は 123 に 456 を掛けた結果から 789 を引くことを意味します。

回答にはEBNF記法に沿った下記のコードを用いることができます。

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

void expr(vector<pair<string, string>> &a, vector<pair<string,string>> &t, int &i);
void number(vector<pair<string, string>> &a, vector<pair<string,string>> &t, int &i);

void expr(vector<pair<string, string>> &a, vector<pair<string,string>> &t, int &i) {
    number(a, t, i);

    /* ここを埋める */

    return;
}

void number(vector<pair<string, string>> &a, vector<pair<string,string>> &t, int &i) {

    /* ここを埋める */

    return;
}

int main(void) {
    int n;
    cin >> n;
    vector<pair<string,string>> a(n);
    for(int i = 0; i < n; i++) {
        string v, t;
        cin >> v >> t;
        a[i] = make_pair(v,t);
    }
    int i = 0;
    vector<pair<string,string>> t;
    expr(a, t, i);
    cout << t.size() << endl;
    for(pair<string,string> c : t) {
        cout << c.first << " " << c.second << endl;
    }

    return 0;
}

def expr(a, t, i):
    i = number(a, t, i)
    
    """ ここを埋める """
    
    return

def number(a, t, i):
    
    """ ここを埋める """
    
    return i

if __name__ == "__main__":
    n = int(input())
    a = []
    for _ in range(n):
        v, t = input().split()
        a.append((v, t))
    i = 0
    t = []
    expr(a, t, i)
    print(len(t))
    for c in t:
        print(c[0], c[1])