中置記法の構文解析#5 Python2編（paizaランク B 相当）

()付きの四則演算と剰余算で構成される中置記法の数式 S が文字列で与えられます。S の計算結果を 1 行で出力してください。

なお、式には以下の制約が設けられています。

ある整数 a, b について

・ a / b の計算結果は小数点以下切り捨て

・ a / b において a > 0、b ≧ 0

・ a % b において a > 0、b ≧ 0

数式は以下のEBNFに従って記述されます。

EBNF

<expr>   ::= <term> ( ('+'|'-') <term> )* 
<term>   ::= <factor> ( ('*'|'/'|'%') <factor> )* 
<factor> ::= <number> | ( '(' <expr> ')' )* 
<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 つの <term> と 0 個以上の ( ('+'|'-') <term> ) の組み合わせで構成されており、<term> は 1 つの <factor> と 0 個以上の ( ('*'|'/'|'%') <factor> ) の組み合わせで構成されており、<factor> は 1 つの <number> と 0 個以上の ( '(' <expr> ')' ) の組み合わせで構成されていることを表しています。

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

中置記法について

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

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

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

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

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

int expr(string &s, int &i);
int term(string &s, int &i);
int number(string &s, int &i);

int expr(string &s, int &i) {
    int val = term(s, i);

    /* ここを埋める */

    return val;
}

int term(string &s, int &i) {
    int val = number(s, i);

    /* ここを埋める */

    return val;
}

int number(string &s, int &i) {
    int v = 0;

    /* ここを埋める */

    return v;
}

int main() {
    string s;
    cin >> s;
    int i = 0;
    cout << expr(s, i) << endl;

    return 0;
}

def expr(s, i):
    [val, i] = number(s, i)
    
    """ ここを埋める """
    
    return val

def number(s, i):
    v = 0
    
    """ ここを埋める """
    
    return [v, i]

if __name__ == "__main__":
    s = input()
    i = 0
    print(expr(s, i))