华为OD机考题目《仿LISP运算》200分题目

接上一篇帖子 https://www.nowcoder.com/discuss/960131

在

牛客大神 @唐浮的这个帖子里： https://www.nowcoder.com/discuss/940385

第三道题《仿LISP运算》这道题，出于个人兴趣，做了一下，发现还挺难，做了半个多小时。

下图是唐浮帖子中截出来的：

用通俗的语言讲一下这道题，是给你提供一个表达式，格式是 (op p1 p2)

首先，格式是用括号包起来的， op 是一个操作符，可能出现的枚举值是 add/sub/mul/div 分别表示加减乘除，其中除有点特殊，如果分母是0，则输出 error , 遇到除不尽的，则向下取整（需要注意， 3/2 向下取整等于 1，但是 -3/2 向下取整是 -2 ）。

其次 p1 p2 是两个元素，它们可能也是一个表达式，比如：

(add (add 0 1) (add 0 -3))

此时 op= add ， p1 = (add 0 1) ， p2 = (add 0 -3)

对于p1来讲，它的 op = add ，它的p1 = 0 ，它的 p2 = 1 ，以此类推。

思路：

对于非嵌套的情况来讲，应该是一个很简单的算法，我们将其定义成一个函数 lispCalc（string& str）

当存在嵌套的情况时，我们应该找到最内层的元素，它一定是一个非嵌套的表达式，然后用 listCalc 把它计算出来，然后把原字符串中，这一段表达式替换成listCalc计算出来的数字，然后以此递归。

假设用例是这样的：

(add 1 (div (sub 1 (mul (add 8 1) 1)) (sub 5 2)))

我们先找到最内层（第一个或者最后一个均可，我为了简单，我找最后一个）的表达式 (sub 5 2) 。怎么找呢？我就找最后一个左括号的位置作为 left，然后从这个left位置找第一个右括号 right，left到 right之间就是我要找的表达式了。

然后用listCalc函数将其计算出来，得到结果 3 ，然后将这段字符串替换为3，得到：

(add 1 (div (sub 1 (mul (add 8 1) 1)) 3))

然后递归，继续找最后一个表达式，此时，应该找出的是 (add 8 1)

此时，将 (add 8 1) 计算出来，得到 9，然后替换进去，得到

(add 1 (div (sub 1 (mul 9 1)) 3))

然后以此类推，得到：

(add 1 (div (sub 1 8) 3))
(add 1 (div -7 3))
(add 1 -3)
最终得到一个原子表达式，再调用 listCalc，得到 -2 ，此时，字符串已经没有更多的括号了，即 left = npos了，此时，递归结束，打印 -2 。

我尝试写了一下代码，但并没有基于上面思路表达的那么完美，代码有点乱，大家将就看一下：

我的main函数：

int main()
{
    string str;
    //cin >> str;  //cin会导致遇到空格就截断，所以要用getlin
    std::getline(cin, str);
    lispCalc(str);
    return 0;
}

listCalc 函数的实现：

int lispCalc(string& str)
{
    string::size_type left = str.find_last_of('(');//不会找不到，所以不判断npos情况
    string::size_type right = str.find(')', left);//不会找不到，所以不判断npos情况
    string op = str.substr(left + 1, 3);//因为运算符固定长度是3
    string::size_type spc = str.find_first_of(' ', left + 5);
    int p1 = stoi(str.substr(left + 5, spc- left -5));
    //spc = str.find_first_of(' ', spc+1);
    int p2 = stoi(str.substr(spc+1, right-spc-1));
    int result = 0;
    if (op == "add")
    {
        result = p1 + p2;
    }
    else if(op == "sub")
    {
        result = p1 - p2;
    }
    else if(op == "mul")
    {
        result = p1 * p2;
    }
    else if(op == "div")
    {
                //如果除法分母是0，则输出error，再也不用递归了，也不用再计算了。
        if (p2 == 0)
        {
            cout << "error" << endl;
            return 0;
        }
        result = divFun(p1, p2);//这里自己实现了一个 向下取整的函数
    }
    else
    {
        return 0;
    }

    if (left == str.find_first_of('('))
    {
        cout << result << endl;
        return result;
    }
        // 将 result 替换原来的字符串那部分，我不太会用replace函数，所以用的本办法。
    string tmp = str.substr(0, left );
    char data[32] = { 0 };
    sprintf_s(data, "%d", result);
    tmp += data;
    tmp += str.substr(right + 1);
    str = tmp;
        //递归继续
    return lispCalc(str);
}

向下取整的函数：

// 向下取整
int divFun(int a, int b) {
    if (a * b > 0 || a % b == 0) {
        return a / b;
    }
    else {
        return a / b - 1;
    }
}

注意：在c++的cpp文件中，被调用的方法的实现一定要在调用它的方法上面。（因为没有在头文件声明）。

上面代码运营结果（为了避免每次都要重启，我加了个无限while循环）：

其他语言，我在网上找了一些源码，正确性暂无法保证，仅供参考：

import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(calc(s));
    }
 
    //获取一个表达式，返回其运算结果
    public static String calc(String s) {
        //如果有括号那么首先拆分括号
        if (s.charAt(0) == '(') {
            while (s.charAt(0) == '(')
                s = s.substring(1, s.length() - 1);
        }
        //是纯数字还是表达式还是error？
        if (s.equals("error"))
            return "error";
        //是纯数字吗？正负数
        if ((s.charAt(0) >= '0' && s.charAt(0) <= '9') || (s.charAt(0) == '-'))
            return s;
        //是表达式
        String op = s.substring(0, 3);
        String p1, p2;
        //p1有括号吗，有括号可能有空格，没括号必定没空格
        //如果没括号
        int index = 4;
        if (s.charAt(index) != '(') {
            while (index < s.length() && s.charAt(index) != ' ')
                index++;
        } else {
            //左括号剩余个数
            int left_bracket_count = 0;
            while (true) {
                if (s.charAt(index) == '(')
                    left_bracket_count++;
                if (s.charAt(index) == ')')
                    left_bracket_count--;
                index++;
                if (left_bracket_count == 0)
                    break;
            }
        }
        p1 = s.substring(4, index);
        p2 = s.substring(index + 1);
        //纯数字
        String p1_result = calc(p1);
        String p2_result = calc(p2);
        if (p1.equals("error") || p2.equals("error") || p1_result.equals("error") || p2_result.equals("error"))
            return "error";
        switch (op) {
            case "add":
                return String.valueOf(Integer.parseInt(p1_result) + Integer.parseInt(p2_result));
            case "sub":
                return String.valueOf(Integer.parseInt(p1_result) - Integer.parseInt(p2_result));
            case "mul":
                return String.valueOf(Integer.parseInt(p1_result) * Integer.parseInt(p2_result));
            case "div":
                if (Integer.parseInt(p2_result) == 0)
                    return "error";
                return String.valueOf(Integer.parseInt(p1_result) / Integer.parseInt(p2_result));
        }
        return "error";
    }
 
}

欢迎大家讨论。