Dimensional Analysis

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem D: Dimensional Analysis

量の次元とは、相異なる量の間の関係式から具体的数値を無視して量の種類とそのべき乗だけに着目した概念である。具体的には定数係数を無視した等式として、次元の関係式を表す。すなわち、量 q の次元を[ q ]と表せば、以下のようないくつかの次元の関係式が例示できる。

  • [面積] = [長さ]2
  • [体積] = [長さ]3
  • [速さ] = [長さ][時間]-1
  • [加速度] = [長さ][時間]-2
  • [力] = [質量][長さ][時間]-2
  • [仕事] = [質量][長さ]2[時間]-2

(Wikipedia 「量」より抜粋 URL http://ja.wikipedia.org/wiki/%E9%87%8F)

量は基本量と組み立て量に分類される。 この問題ではn個の基本量とm個の組立量が与えられる。 与えられたm個の組立量の次元はすべてn個の基本量の次元の積で表すことができる。 また基本量の次元の積で2つの次元を表したとき、各基本量の指数がすべて一致すればその二つの次元は等しいと言える。

式と変数の量と量の次元についての情報が与えられるので、 式を解析しその次元が表す量の名称を答えよ。 名称が定義されてない場合はundefinedと出力せよ。 また、計算過程で異なる二つの次元の加算もしくは減算するような演算のことを”不正な演算”の定義する。 ”不正な演算”があればerrorと出力せよ。 与えられる式は以下を満たす。

  1. すべての変数は組立量の次元に割り当てられている。
  2. 式は四則演算+, -, /, *とカッコ()と変数のみを含む。
  3. 四則演算はよく知られているもので、正しく記述されているものとする。厳密には以下のBNFに従う。 また単項演算子は使用されない。(x * (-a))などは存在しない。
<formula>::=<term>|<formula>+<term>|<formula>-<term>
<term>::=<factor>|<term>*<factor>|<term>/<factor>
<factor>::=<variable>|(<formula>)
<variable>::=<string>
<string>::=<char>|<string><char>
<char>::=a~z|A~Z
<formula>が式を表し、<variable>が変数名を表す。

Input

入力は複数のデータセットで構成されている。 データセットの数は1,000個を超えない。 データセットは以下の形式で与えられる。

n m p
derived1
d1,1 d1,2 d1,3.... d1,n
derived2
d2,1 d2,2 d2,3.... d2,n
...
derivedm
dm,1 dm,2 dm,3.... dm,n
formula
v1 D1
v2 D2
...
vp Dp

n(1≤n≤5)は基本量の数 m(1≤m≤10) は組立量の数 p(1≤p≤15)は変数の種類数を示す。 derivediはi番目の組立量の名前である。アルファベット大文字や小文字から構成され長さは20文字を超えない。 di,j(-10≤di,j≤10)はi番目の組立量のj番目の基本量の次元を表す(1≤i≤m, 1≤j≤n)。 同じ組立量の名称は複数回現れないが、同じ次元の組立量が複数回現れることがある。 formulaは解析を行う数式を表す。長さは100文字を超えない。 viは変数名を表す。アルファベット大文字や小文字から構成され長さは20文字を超えない。 Diはviの次元の名称を表す。すでに与えられた組立量の名称であることが保証されている。 入力中の数(n, m, p, d)はすべて整数である。 入力の終わりは、3個の0がそれぞれ一文字の空白で区切られる一行で示される。

Output

一行に式を解析しその次元の名称を出力せよ。 もし、その次元の名称が複数存在する場合は最後に定義したものを出力せよ。 名称が定義されてない場合はundefinedと出力せよ。 また、不正な演算が含まれる場合はerrorと出力せよ。

Sample Input

2 3 2
length
1 0
time
0 1
speed
1 -1
a/b
a length
b time
2 3 3
length
1 0
time
0 1
speed
1 -1
a/b+c
a length
b time
c speed
2 3 3
length
1 0
time
0 1
speed
1 -1
a/b+c
a length
b time
c time
2 3 2
length
1 0
time
0 1
speed
1 -1
a/b/b
a length
b time
3 6 6
speed
1 -1 0
acceleration
1 -2 0
force
1 -2 1
length
1 0 0
time
0 1 0
weight
0 0 1
((v+l/t)+a*t)/(t*t)*w*t+f+w*a
v speed
l length
a acceleration
t time
w weight
f force
0 0 0

Sample Output

speed
speed
error
undefined
force

Source: Ritsumeikan University Programming Camp 2012 , Day 1, Shiga, Japan, 2012-03-13