1090 - APL Lives!

发布时间:2017-1-21 2:06:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1090 - APL Lives!",主要涉及到1090 - APL Lives!方面的内容,对于1090 - APL Lives!感兴趣的同学可以参考一下。

APL is an array programming language that uses a notation invented by Ken Iverson in 1957. In this problem we consider only a small subset of the language which we call apl (that is, small APL). Each apl expression appears on a line by itself and each expression has a value, which is displayed immediately after the expression is entered. Operators in apl do not have precedence like those in C, C++, or Java, but instead are applied right to left. However, parentheses may be used to control evaluation order. Similarly, operands for binary operators are evaluated in right to left order. Here are some examples of apl expressions. var = 1 2 3 Store the vector 1 2 3 in var, replacing its previous value. The   value of the expression is 1 2 3. The left operand of the =   operator must be a variable. var + 4 Display the value of var with 4 added to each of its elements   (result: 5 6 7); the stored version of var is not modified. - / var Display the value of var as if a - operator had been   inserted between each of its elements on each row (result: 2). If var   has two dimensions, the result is a vector. If var has three   dimensions, the result is a two-dimensional array. * / and   + / have analogous behaviors. iota 5 Generate a vector with the values 1 2 3 4 5. 2 2 rho 1 2 3 4 Reshape the vector 1 2 3 4 into a 2 by 2 array; 1 and 2 are in   the first row, and 3 and 4 are in the second row. 2 2 rho 1 2 3 4 5 6 Same result as above. 2 3 rho 1 2 3 4 Another reshaping, yielding a first row with 1 2 3 and a second   row with 4 1 2; if the right argument does not have a sufficient   number of elements, then the elements of the right operand are   reused starting from the beginning, in row-major order. 2 drop iota 5 Result: 3 4 5. Drops the two leading elements from iota 5. 1 2 * 3 4 Result: 3 8. Illustrates element-wise multiplication. Operands   must be conformable - either they have the same shape, or at least   one must be a one-element vector (see second example). ( ( a = 1 ) drop 1 2 3 ) - 5 Result: -3 -2. Illustrates use of parentheses. a + ( a = 5 ) + a + ( a = 6 ) Result: 22. Illustrates evaluation order In this problem you are to write an interpreter for apl. Integers in the input are non-negative and less than 104. All computed integer values (including intermediate values) have absolute values less than 104. The number of entries in any matrix is always less than or equal to 104. Variable names consist of one to three alphabetic lowercase characters, and the names iota, rho, and drop are always interpreted as operators. Exactly one space separates elements of statements (constants, variables, operators, and parentheses). Constants in the input are vectors. All intermediate values are one, two, or three-dimensional arrays with positive dimensions. This restricts some operand ranges: ``2 0 rho 1 2 3", ``2 3 2 1 rho 5", and ``3 drop iota 3" are illegal. The only arithmetic operators provided are + (addition), - (subtraction), and *(multiplication). Their operands are conformable as illustrated in the examples. Observe that ``1 1 rho 1" and ``1 rho 1" have different shapes. The operand for iota evaluates to a one-element positive vector. The left operand of drop evaluates to a one-element non-negative vector and its right operand evaluates to a vector. Both operands of rho evaluate to vectors. Input  The input contains several test cases, each on a line by itself. The values of variables assigned in one test case are available for use in following test cases. No expression exceeds 80 characters in length, including space characters. No test case produces an invalid result (for example, an empty vector). The last test case is followed by a line containing the single character `#'. Output  For each test case, display a line containing the case number and the input line. Then, starting on the next line, display the result of evaluating the expression. Vectors display as a single line of integers; m x narrays display as m lines of n values, and m x n x p arrays display as m arrays of size n x p, with a blank line separating the n x p arrays. Values on the same line should be separated by white space but need not be aligned in columns. Sample Input  var = 1 2 3 var + 4 - / var iota 5 2 2 rho 1 2 3 4 2 3 rho 1 2 3 4 2 drop iota 4 1 2 * 3 4 ( ( a = 1 ) drop 1 2 3 ) - 5 a + ( a = 5 ) + a + ( a = 6 ) ( 2 2 rho 2 drop iota 6 ) + 100 1 2 3 + 4 5 6 2 3 rho 1 2 3 4 5 + 1 2 3 4 5 + / 2 3 4 rho iota 2 * 3 * 4 ( 2 4 5 rho iota 2 * 4 * 5 ) - 99 # Sample Output  Case 1: var = 1 2 3 1 2 3 Case 2: var + 4 5 6 7 Case 3: - / var 2 Case 4: iota 5 1 2 3 4 5 Case 5: 2 2 rho 1 2 3 4 1 2 3 4 Case 6: 2 3 rho 1 2 3 4 1 2 3 4 1 2 Case 7: 2 drop iota 4 3 4 Case 8: 1 2 * 3 4 3 8 Case 9: ( ( a = 1 ) drop 1 2 3 ) - 5 -3 -2 Case 10: a + ( a = 5 ) + a + ( a = 6 ) 22 Case 11: ( 2 2 rho 2 drop iota 6 ) + 100 103 104 105 106 Case 12: 1 2 3 + 4 5 6 5 7 9 Case 13: 2 3 rho 1 2 3 4 5 + 1 2 3 4 5 2 4 6 8 10 2 Case 14: + / 2 3 4 rho iota 2 * 3 * 4 10 26 42 58 74 90 Case 15: ( 2 4 5 rho iota 2 * 4 * 5 ) - 99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -88 -87 -86 -85 -84 -83 -82 -81 -80 -79 -78 -77 -76 -75 -74 -73 -72 -71 -70 -69 -68 -67 -66 -65 -64 -63 -62 -61 -60 -59 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<string> #include<iostream> #include<map> using namespace std; const int MAXN=10010; struct Tmatrix { int n,m,k,f,d; int a[MAXN]; int &get(int i,int j,int k1) { return a[i*m*k+j*k+k1]; } }; int n,m; map<string,int> hash1; Tmatrix a[100]; string b[100]; void init() { hash1.clear(); m=0; } int getNum(string &s) { if(hash1[s]==0) hash1[s]=++m; return hash1[s]; } void readln() { n=0; char c=' '; while(c==' ') { cin>>b[++n]; c=getchar(); } } void deal(int &l,int &r) { int i,t; while(1) { if(b[l]!="(" || b[r]!=")") return; t=0; for(i=l;i<=r;++i) if(b[i]=="(") ++t; else if(b[i]==")") --t; else if(t==0) return; ++l; --r; } } bool isNum(string &s) { int i,l=s.size(); for(i=0;i<l;++i) if(s[i]<'0'||s[i]>'9') return false; return true; } int strToNum(string &s) { int i,l=s.size(); int t=0; for(i=0;i<l;++i) t=t*10+s[i]-'0'; return t; } bool isAllNum(int l,int r) { for(int i=l;i<=r;++i) if(!isNum(b[i])) return false; return true; } Tmatrix operator + (Tmatrix m1,Tmatrix m2) { if(m1.f>0) m1=a[m1.f]; if(m2.f>0) m2=a[m2.f]; Tmatrix tmp=m1; int i,j,k; if(m2.n*m2.m*m2.k==1) { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)+=m2.get(0,0,0); } else if(m1.n*m1.m*m1.k==1) { tmp=m2; for(i=0;i<m2.n;++i) for(j=0;j<m2.m;++j) for(k=0;k<m2.k;++k) tmp.get(i,j,k)+=m1.get(0,0,0); } else { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)+=m2.get(i,j,k); } return tmp; } Tmatrix operator - (Tmatrix m1,Tmatrix m2) { if(m1.f>0) m1=a[m1.f]; if(m2.f>0) m2=a[m2.f]; Tmatrix tmp=m1; int i,j,k; if(m2.n*m2.m*m2.k==1) { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)-=m2.get(0,0,0); } else if(m1.n*m1.m*m1.k==1) { tmp=m2; for(i=0;i<m2.n;++i) for(j=0;j<m2.m;++j) for(k=0;k<m2.k;++k) tmp.get(i,j,k)=m1.get(0,0,0)-tmp.get(i,j,k); } else { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)-=m2.get(i,j,k); } return tmp; } Tmatrix operator * (Tmatrix m1,Tmatrix m2) { if(m1.f>0) m1=a[m1.f]; if(m2.f>0) m2=a[m2.f]; Tmatrix tmp=m1; int i,j,k; if(m2.n*m2.m*m2.k==1) { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)*=m2.get(0,0,0); } else if(m1.n*m1.m*m1.k==1) { tmp=m2; for(i=0;i<m2.n;++i) for(j=0;j<m2.m;++j) for(k=0;k<m2.k;++k) tmp.get(i,j,k)*=m1.get(0,0,0); } else { for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) for(k=0;k<m1.k;++k) tmp.get(i,j,k)*=m2.get(i,j,k); } return tmp; } Tmatrix rho(Tmatrix m1,Tmatrix m2) { if(m1.f>0) m1=a[m1.f]; if(m2.f>0) m2=a[m2.f]; Tmatrix tmp; tmp.f=0; tmp.n=m1.get(0,0,0); tmp.m=m1.get(1,0,0); tmp.k=m1.get(2,0,0); if(m1.n<3) tmp.k=1; if(m1.n<2) tmp.m=1; tmp.d=m1.n; int i,j,k,l=0; for(i=0;i<tmp.n;++i) for(j=0;j<tmp.m;++j) for(k=0;k<tmp.k;++k) { tmp.get(i,j,k)=m2.get(l,0,0); l=(l+1)%m2.n; } return tmp; } Tmatrix iota(Tmatrix m1) { if(m1.f>0) m1=a[m1.f]; Tmatrix tmp; tmp.f=0; tmp.n=m1.get(0,0,0); tmp.m=1; tmp.k=1; tmp.d=1; for(int i=0;i<tmp.n;++i) tmp.get(i,0,0)=i+1; return tmp; } Tmatrix drop(Tmatrix m1,Tmatrix m2) { if(m1.f>0) m1=a[m1.f]; if(m2.f>0) m2=a[m2.f]; Tmatrix tmp=m2; tmp.f=0; int i,j,k; tmp.n-=m1.get(0,0,0); for(i=0;i<m2.n-m1.get(0,0,0);++i) for(j=0;j<m2.m;++j) for(k=0;k<m2.k;++k) tmp.get(i,j,k)=tmp.get(i+m1.get(0,0,0),j,k); return tmp; } Tmatrix op1(Tmatrix m1) { if(m1.f>0) m1=a[m1.f]; Tmatrix tmp=m1; if(tmp.d>1) --tmp.d; int i,j,k; if(m1.d==3) { tmp.k=1; for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) { tmp.get(i,j,0)=m1.get(i,j,m1.k-1); for(k=m1.k-2;k>=0;--k) tmp.get(i,j,0)=m1.get(i,j,k)+tmp.get(i,j,0); } } else if(m1.d==2) { tmp.m=1; for(i=0;i<m1.n;++i) { tmp.get(i,0,0)=m1.get(i,m1.m-1,0); for(k=m1.m-2;k>=0;--k) tmp.get(i,0,0)=m1.get(i,k,0)+tmp.get(i,0,0); } } else { tmp.n=1; { tmp.get(0,0,0)=m1.get(m1.n-1,0,0); for(k=m1.n-2;k>=0;--k) tmp.get(0,0,0)=m1.get(k,0,0)+tmp.get(0,0,0); } } return tmp; } Tmatrix op2(Tmatrix m1) { if(m1.f>0) m1=a[m1.f]; Tmatrix tmp=m1; if(tmp.d>1) --tmp.d; int i,j,k; if(m1.d==3) { tmp.k=1; for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) { tmp.get(i,j,0)=m1.get(i,j,m1.k-1); for(k=m1.k-2;k>=0;--k) tmp.get(i,j,0)=m1.get(i,j,k)-tmp.get(i,j,0); } } else if(m1.d==2) { tmp.m=1; for(i=0;i<m1.n;++i) { tmp.get(i,0,0)=m1.get(i,m1.m-1,0); for(k=m1.m-2;k>=0;--k) tmp.get(i,0,0)=m1.get(i,k,0)-tmp.get(i,0,0); } } else { tmp.n=1; { tmp.get(0,0,0)=m1.get(m1.n-1,0,0); for(k=m1.n-2;k>=0;--k) tmp.get(0,0,0)=m1.get(k,0,0)-tmp.get(0,0,0); } } return tmp; } Tmatrix op3(Tmatrix m1) { if(m1.f>0) m1=a[m1.f]; Tmatrix tmp=m1; if(tmp.d>1) --tmp.d; int i,j,k; if(m1.d==3) { tmp.k=1; for(i=0;i<m1.n;++i) for(j=0;j<m1.m;++j) { tmp.get(i,j,0)=m1.get(i,j,m1.k-1); for(k=m1.k-2;k>=0;--k) tmp.get(i,j,0)=m1.get(i,j,k)*tmp.get(i,j,0); } } else if(m1.d==2) { tmp.m=1; for(i=0;i<m1.n;++i) { tmp.get(i,0,0)=m1.get(i,m1.m-1,0); for(k=m1.m-2;k>=0;--k) tmp.get(i,0,0)=m1.get(i,k,0)*tmp.get(i,0,0); } } else { tmp.n=1; { tmp.get(0,0,0)=m1.get(m1.n-1,0,0); for(k=m1.n-2;k>=0;--k) tmp.get(0,0,0)=m1.get(k,0,0)*tmp.get(0,0,0); } } return tmp; } Tmatrix calc(int l,int r) { deal(l,r); int i,j,t=0; Tmatrix tmp; if(isAllNum(l,r)) { tmp.n=tmp.f=0; tmp.m=tmp.k=tmp.d=1; for(i=l;i<=r;i++) tmp.get(tmp.n++,0,0)=strToNum(b[i]); return tmp; } if(l==r) { tmp.f=getNum(b[l]); return tmp; } j=-1; for(i=l;i<=r;++i) if(b[i]==")") ++t; else if(b[i]=="(") --t; else if(t==0&&(i>l)&& (b[i]=="+" || b[i]=="-" ||b[i]=="*"||b[i]=="=" ||b[i]=="iota"||b[i]=="drop" ||b[i]=="rho")) { j=i; break; } Tmatrix m1,m2; if(b[l]=="iota") { m1=calc(l+1,r); return iota(m1); } if(b[l+1]=="/") { m1=calc(l+2,r); if(b[l]=="+") return op1(m1); if(b[l]=="-") return op2(m1); if(b[l]=="*") return op3(m1); } if(b[j]=="+") { m2=calc(j+1,r); if(m2.f>0) m2=a[m2.f]; m1=calc(l,j-1); return m1+m2; } if(b[j]=="-") { m2=calc(j+1,r); if(m2.f>0) m2=a[m2.f]; m1=calc(l,j-1); return m1-m2; } if(b[j]=="*") { m2=calc(j+1,r); if(m2.f>0) m2=a[m2.f]; m1=calc(l,j-1); return m1*m2; } if(b[j]=="=") { m2=calc(j+1,r); m1=calc(l,j-1); a[m1.f]=m2; return m2; } if(b[j]=="rho") { m2=calc(j+1,r); if(m2.f>0) m2=a[m2.f]; m1=calc(l,j-1); return rho(m1,m2); } if(b[j]=="drop") { m2=calc(j+1,r); if(m2.f>0) m2=a[m2.f]; m1=calc(l,j-1); return drop(m1,m2); } } void solve() { int CASE=0; readln(); int i,j,k; Tmatrix tmp; while(b[1]!="#") { cout<<"Case "<<(++CASE)<<":"; for(i=1;i<=n;++i) cout<<" "<<b[i]; cout<<endl; tmp=calc(1,n); if(tmp.f>0) tmp=a[tmp.f]; if(tmp.d==3) { for(j=0;j<tmp.m;++j) { for(k=0;k<tmp.k;++k) cout<<" "<<tmp.get(0,j,k); cout<<endl; } for(i=1;i<tmp.n;++i) { cout<<endl; for(j=0;j<tmp.m;++j) { for(k=0;k<tmp.k;++k) cout<<" "<<tmp.get(i,j,k); cout<<endl; } } } else if(tmp.d==2) { for(j=0;j<tmp.n;++j) { for(k=0;k<tmp.m;++k) cout<<" "<<tmp.get(j,k,0); cout<<endl; } } else { for(k=0;k<tmp.n;++k) cout<<" "<<tmp.get(k,0,0); cout<<endl; } //fupdate(stdout); readln(); } } int main() { init(); solve(); return 0; }

上一篇:linux下进程编程综述
下一篇:Job的提交—客户端

相关文章

关键词: 1090 - APL Lives!

相关评论