问题 D: lisp表达式求值
时间限制: 1 Sec 内存限制: 128 MB
提交: 105 解决: 43
[提交][状态][讨论版]
题目描述
lisp是一种非常古老的计算机语言，是由约翰·麦卡锡在1960年左右创造的一种基于λ演算的函数式编程语言，其语法如下：
(+ 2 3 4 5)
表示2+3+4+5，其值为14
(* 2 3 5)
表示2*3*5，其值为30
减法可以表示为：
(- 2 3 4)
表示：2-3-4=-5
即括弧中第一个符号为运算符，后面是操作数，改运算也可以嵌套，比如
(* (+ 2 3) 6)
表示先计算2+3=5，然后再5*6=30
麦卡锡当初提出了一套理论，其核心是一个eval函数，1958年年底，麦卡锡的一个学生史蒂夫•拉塞尔 看到了eval函数的定义，意识到如果把它翻译成机器语言，就可以把Lisp解释器做出来。这在当时是非常令人吃惊的事。麦卡锡后来回忆：拉塞尔对我说：“我想把eval编成程序……”我告诉他，别把理论和实践混淆，eval只是用来读的，不是用来做计算的。但是他执意要做，并且还真的做出来了。就是说，他把我论文中的eval编译成了[IBM] 704计算机的机器码，修正了bug，然后对外宣布做出了Lisp语言的一种解释器，这倒没有说错，确实如此。所以，从那个时候开始，Lisp语言就基本上是它现在的样子了……
现在，请你完成这个任务， 给出一个lisp表达式，计算出其结果
输入
一个lisp表达式
输出
该表达式的值
样例输入
(+ 2 (* 3 4) (- 3 5))
样例输出
12
#include<stdio.h>
#include<string.h>
char s[],ch;
int n,k;
long dfs(int t,char c)
{
int i=,j,a[];
long ans;
while (s[k]!=')')
{
if (s[k]=='(')
{
k++;
while (s[k]==' ') k++;
ch=s[k];
i++;
a[i]=dfs(t+,ch);
}
else if (s[k]==' ') k++;
else if (s[k]>=''&&s[k]<='')
{
i++;
a[i]=s[k]-;
k++;
}
else k++;
}
ans=a[];
if (c=='+')
for (j=;j<=i;j++)
ans+=a[j];
if (c=='-')
for (j=;j<=i;j++)
ans-=a[j];
if (c=='*')
for (j=;j<=i;j++)
ans*=a[j];
if (c=='/')
for (j=;j<=i;j++)
ans/=a[j];
k++;
return ans;
} int main()
{
gets(s);
n=strlen(s);
k=;
while (s[k]!='(')
k++;
k++;
while (s[k]==' ')
k++;
ch=s[k];
printf("%ld\n",dfs(,ch));
return ;
}