hiho一下第87周《S-expression》题目分析

1
0

题目大意

给定一个简化的Lisp语句,求该语句的值。 在简化版本的Lisp语句中只包含3种运算:

  • (f x y): 表示对x,y进行f运算。f可能为+-*/ (Div)四种数值计算,也可能是>=<的比较运算
  • (if a x y): 表示选择运算,根据a的值为truefalse来决定返回x或者y
  • (let (x a) b): 表示设定变量x的值为a,其作用范围为b,并且计算b的具体值

解题思路

本题是一个较为复杂的模拟题。需要理清所有的情况分别解决,代码量稍大。

由于在给定的Lisp语句中任意两个元素之间都存在一个空格,因此我们可以很容易的将每一个元素都找出来。

我们用一个数组将所有的元素都记录下来,得到element[1 .. n]

element[i]可能是一个(或者),可能是let,if等关键词,也可能是一个数字或一个只包含小写字母的字符串。

同时Lisp的语句是满足递归定义的,因此我们同样采用递归的方式去处理出整个式子的值:

getValue(left, right):
    // 我们当前处理的区间为 element[left..right]
    If (element[ left ] == '(') Then
        // 当前区间为一个运算
        // ..todo
    End If
    If (element[ left ] is a number) Then
        // 当前区间为一个数字,直接返回其值即可
        return element[ left ]
    End If
    If (element[ left ] is a bool) Then
        // element[ left ] == 'true' or 'false'
        // 当前区间为一个布尔类型,直接返回其值即可
        return element[ left ]
    End If
    If (element[ left ] is a variable) Then
        // element[ left ] 为一个字符串,且不属于关键字
        // 此时需要去我们已经知道的变量表中查询这个变量的值
        // 变量表由let运算定义,这里后面会专门讲到
        return findInVariableList(element[ left ])
    End If
    // 当发生任意不合法行为时,返回Error
    Return Error

根据题目描述,一共可能出现3种不同的运算,因此我们对其分别进行处理。从难易程度上来说,最简单是( f x y ),其次是(if a x y),最后是( let (x a) b)。我们依次对其进行处理:

If (element[ left ] == '(') Then
    // 当前区间为一个运算
    If (element[left + 1] == 'if') Then
        // if运算
    End If
    If (element[left + 1] == 'let') Then
        // let运算
    End If

    // ==== (f x y) ====

    op = element[ left + 1 ] // 获取运算符号
    // 接下来获取x, y两个元素,由于这两个元素也有可能是递归定义的
    // 因此我们需要找到op后面连续的两个语句

    // 先处理x
    x_left = left + 2
    If (element[ x_left ] == '(') Then
        // 此时x为一个式子,对应了一个区间,我们需要去找到该左括号对应的右括号
        x_right = findRight(x_left)
    Else
        // 否则x为一个单独的数字,其区间为[x_left,x_left]
        x_right = x_left
    End If
    x = getValue(x_left, x_right)
    If (x == Error) Then
        Return Error
    End If

    // 再处理y
    y_left = x_right + 1
    If (element[ y_left ] == '(') Then
        // 此时y为一个式子,我们需要去找到该左括号对应的右括号
        y_right = findRight(y_left)
    Else
        y_right = y_left
    End If
    y = getValue(y_left, y_right)
    If (y == Error) Then
        Return Error
    End If

    // 接下来返回计算值
    // 需要注意的是,若op == '/'时,y不能等于0
    If (op == '/' and y == 0) Then
        Output("Division By Zero")
        Return Error
    End If
    // 同时还需要判定x, y是否都是数字
    If (x is not number or y is not number) Then
        Output("Type Mismatch")
        Return Error
    End If
    Return (x op y)
End If

其中findRight函数为:

findRight(left):
    cnt = 0 // 记录括号匹配数量
    For i = left .. n
        If (element[i] == '(') Then
            cnt = cnt + 1
        End If
        If (element[i] == ')') Then
            cnt = cnt - 1
            If (cnt == 0) Then
                Return i
            End If
        End If
    End For

这样就处理完成了( f x y ),接下来考虑如何处理if

If (element[left + 1] == 'if') Then
    // if运算
    // 首先计算表达式的值
    a_left = left + 2
    If (element[ a_left ] == '(') Then
        a_right = findRight(a_left)
    Else
        a_right = a_left
    End If
    a = getValue(a_left, a_right)
    If (a == Error) Then
        Return Error
    End If
    If (a is not bool) Then
        Output("Type Mismatch")
        Return Error
    End If

    // 获取x和y,这里需要注意,先不计算x,y的值,只找出区间即可
    // 先处理x
    x_left = a_right + 1
    If (element[ x_left ] == '(') Then
        x_right = findRight(x_left)
    Else
        x_right = x_left
    End If

    // 再处理y
    y_left = x_right + 1
    If (element[ y_left ] == '(') Then
        y_right = findRight(y_left)
    Else
        y_right = y_left
    End If

    // 根据a的值返回对应的值
    If (a == true) Then
        Return getValue(x_left, x_right)
    Else
        Return getValue(y_left, y_right)
    End If

End If

关于此处为什么要先找出区间后计算值,其理由是若语句存在形如(if true 4 x)时,正确结果是返回4,而不是找不到x的值。因为选择语句的存在,导致x这个值就算没有被定义也无所谓。

最后我们来处理最麻烦的let的运算:

这里我们使用了一个栈来存储定义的变量,每次查找时,从栈顶向下查找。以保证在变量名相同时,优先使用后定义的变量。

对于( let ( x 1 ) ( let ( x 2 ) x ) )这样的式子,就能正确的给出x=2的解。

其伪代码:

If (element[left + 1] == 'let') Then
    // let运算
    // 找出定义的部分
    define_left = left + 2
    define_right = findRight(define_left)

    // 获取变量名
    variableName  = element[ define_left + 1 ]
    // 获取变量的值
    variableValue = getValue(define_left + 2, define_right - 1)
    If (variableValue == Error) Then
        Return Error
    End If

    // 将新的变量压入栈
    varStack[top].name  = variableName
    varStack[top].value = variableValue
    top = top + 1

    // 计算b的部分
    tpAns = getValue(define_right + 1, right - 1)

    // 该变量过期,将其出栈
    top = top - 1

    Return tpAns
End If

那么对应查找变量的findInVariableList为:

findInVariableList(variableName):
    For i = top .. 0
        If (varStack[i].name == variableName)
            Return varStack[i].value
        End If
    // 找不到对应的变量
    Output("Unbound Identifier")
    Return Error

至此,所以可能出出现的情况我们已经全部模拟了出来,本题也就迎刃而解了。

还需要注意的是,本题有多组输入数据,务必记得初始化。

8 answer(s)

0

( if 1 1 0 )

0

加油!

0

写的好累啊……

0

终于ac了,写了一晚上加一早上。。。。。 已经感觉自己没有前途了。。。。。

0

其实代码中不需要先找区间后计算值,也不需要专门进行括号匹配,遇到括号直接跳过就行,因为所有的语法都是前缀语法,处理的顺序和字符串读取的顺序是相同的。边扫描字符串边构造语法树,最后遍历语法树以后,根节点存储的就是整个式子的值。

  • 对的,唯一要用到括号的地方是(if a b c )这里了,因为b,c只用计算一个,另一个要跳过,跳的时候用括号来判断跳的距离。

  • 添加评论
  • reply
0

40分,我也无语,能找到的case都试了,输出都是正确的。。。

  • 60了,原来测试用例中有多个空格的情况,比如( + 1 2)

  • 添加评论
  • reply
0

始终都是只能通过20个测试case…无语了…

0

醉了,不知道哪里是错的,为什么没有用例测试错误结果详细说明

write answer 切换为英文 切换为中文


转发分享