题目大意

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

(f x y): 表示对x,y进行f运算。f可能为+、-、*、/ (Div)四种数值计算，也可能是>、=、<的比较运算
(if a x y): 表示选择运算，根据a的值为true或false来决定返回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

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

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

asked 2016-02-27

gtdzx

0