华为OD机试真题-仿LISP计算

题目描述：

LISP 语言唯一的语法就是括号要配对。

形如(OP P1 P2 …)，括号内元素由单个空格分割。

其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型。
注意:

参数 P1,P2 也有可能是另外一个嵌套的 (OP P1 P2…)，当前 OP 类型为 add/sub/mul/div(全小写)，分别代表整数的加减乘除法，简单起见，所有 OP 参数个数均为 2。

举例:

• 输入:(mul 3-7)输出:-21

• 输入:(add 1 2)输出:3

• 输入:(sub(mul 2 4)(div 9 3))输出:5

• 输入:(div 1 0)输出:error

题目涉及数字均为整数，可能为负;

不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转

除零错误时，输出“error”

除法遇除不尽，向下取整，即3/2=1

输入描述

输入为长度不超过512的字符串，用例保证了无语法错误

输出描述

输出计算结果或者“error”

示例1

输入

(div 12 (sub 45 45))

输出

error

说明

45减45得0，12除以0为除零错误，输出error

示例2

输入

(add 1 (div -7 3))

输出

-2

说明

-7除以3向下取整得-3，1加-3得-2

题解

利用栈 进行操作， 遇到 ( 开始进栈 遇到 ) 开始出栈进行计算，计算结果压入栈中
最后栈中剩下的数字就是我们要求的表达式的结果

源码Java

import java.util.Stack;

public class LISP {

	static Input input;
	static {
		input = new Input("(div 12 (sub 45 45))");
		input = new Input("(add 1 (div -7 3))");
	}

	public static void main(String[] args) {
		String s = input.nextLine();

		try{
			int start = 0;
			Stack<String> stack = new Stack<>();
			for (int i = start; i < s.length(); i++) {
				if ('(' == s.charAt(i)) {
					start++;
					continue;
				}
				if (' ' == s.charAt(i)) {
					stack.push(s.substring(start, i));
					start = i + 1;
					continue;
				}
				if (')' == s.charAt(i)) {
					if (Character.isDigit(s.charAt(i-1))) {
						String num2 = s.substring(start, i);
						String num1 = stack.pop();
						String op = stack.pop();
						stack.push(""+cal(op, num1, num2));
					} else {
						String num2 = stack.pop();
						String num1 = stack.pop();
						String op = stack.pop();
						stack.push(""+cal(op, num1, num2));
					}
				}
			}
			System.out.println(stack.pop());
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
	}
	public static int cal(String op, String num1, String num2)  {
		int a = Integer.parseInt(num1);
		int b = Integer.parseInt(num2);
		if("mul".equals(op)) {
			return mul(a, b);
		}
		if ("add".equals(op)) {
			return add(a, b);
		}
		if ("sub".equals(op)) {
			return sub(a, b);
		}
		if ("div".equals(op)) {
			return div(a, b);
		}
		throw new RuntimeException("Unknown operator: " + op);
	}

	// 输入:(mul 3-7)输出:-21
	public static int mul(int a, int b) {
		return a * b;
	}

	// 输入:(add 1 2)输出:3
	public static int add(int a, int b) {
		return a + b;
	}

	// 输入:(sub(mul 2 4)(div 9 3))输出:5
	public static int sub(int a, int b) {
		return a - b;
	}

	//输入:(div 1 0)输出:error
	public static int div(int a, int b) {
		if (b == 0) {
			throw new RuntimeException("error");
		}
		int result = a / b;
		if (result < 0) {
			if (a%b < 0) {
				return a/b - 1;
			}
		}
		return a / b;
	}
}