構文解析

問題 パソコン甲子園2005 17 かしこい電卓

式を入力すると、その値を計算して出力し終了するプログラムを作成してください。

• 式は数値、演算記号、かっこからなり、=で終わります。
• 数値は常に１桁の数字とします。（おもしろくないので、この条件は省略します）
• 演算記号は+,-,*,/ の4つで、それぞれ、加算、減算、乗算、除算を表します。
• 四則演算の優先順位は通常の計算と同じとします。すなわち乗算・除算は加算・減算よりも優先され、 同じ優先順位なら左から計算が行われます。
• 0での割り算は発生しないものとします。
• 演算はすべて整数で行い、小数点以下切捨てとします。
• 入力される式の長さは40文字以内とします。

入力例

3
4-2*3=
4*(8+4+3)=
((1+1-1)*123)+(2*3-10)/2+25=

出力例

-2
60
146

解説

以下のEＢＮＦ(表記が正しいかは微妙です)で定義された文法を、トップダウン構文解析法で、再帰的にパースします。詳しい解説は、１０分で書ける、お手軽パーザーがとても参考になります。

expression = term { ('+'|'-') term }
term = factor { ('*'|'/') factor }
factor = '(' expression ')' | number
number = { digit }

EBNFは、言語を形式的に定義するための表記法で、文字列や数列等の生成規則によって定義されます。例えば、 上記の　expression とは、term または　term のあとに +　または - を演算子とした term がいくつか繰り返されることを意味します。term　の生成規則についても同様です。また、factor は ( ) で囲まれた expression または 数字 になります。 これらの規則を、それぞれ再帰関数により実装します。

サンプルプログラム

001 #include<iostream>
002 #include<string>
003 
004 using namespace std;
005 
006 int expression();
007 int term();
008 int factor();
009 
010 string exp;
011 int p;
012 
013 int expression(){
014     int value = term();
015     while( exp[p] == '+' || exp[p] == '-' ){
016         if ( exp[p] == '+' ) { p++; value += term(); }
017         else { p++; value -= term(); }
018     }
019     return value;
020 }
021 
022 int term(){
023     int value = factor();
024     while( exp[p] == '*' || exp[p] == '/' ){
025         if ( exp[p] == '*' ) { p++; value *= factor(); }
026         else { p++; value /= factor(); }
027     }
028     return value;
029 }
030 
031 int factor(){
032     int value = 0;
033     if ( exp[p] == '(' ){
034         p++; value = expression(); p++;
035     } else {
036         while( isdigit(exp[p]) ) { value = value*10 + exp[p++] - '0';}
037     }
038     return value;
039 }
040 
041 int main(){
042     int tcase; cin >> tcase;
043     for ( int i = 0; i < tcase; i++ ){
044         cin >> exp;
045         p = 0;
046         cout << expression() << endl;
047     }
048     return 0;
049 }