某公司面试笔试题目(在线

笔编程题两个

1.用冒泡算法实现整数数组排序，

2.实现一个计算器可以计算加减乘除

要求是考虑程序的健壮性

冒泡排序:

比较相邻两个数的大小，如果前者比后者大，则交换两者。

先来一个最简单的例子 3,2,1

对[0,2]区间内相邻的数进行冒泡操作， 3和2交换位置，3和1交换位置 2,1,3

对[0,1]区间内相邻的数进行冒泡操作，2和1交换位置， 1,2,3

对[0,0]区间内相邻的数进行冒泡操作，右端点到0,结束。

外循环: 区间的右端点r从len-1逐渐减小到0，

内循环: 对[0,r]内相邻的数进行冒泡操作。 j由0->r-1,比较item[j] 和 item[j+1]的大小

public class Sort {

    public static void main(String[] args) {
        int[] itmes = new int[]{3,2,1} ;
        sort(itmes);
        System.out.println();

    }


    public static void sort(int[] items) {
        int length = items.length;
        for (int r = length - 1; r > 0; r--) {
            for (int j = 0; j <= r - 1; j++) {
                if (items[j] > items[j + 1]) {
                    int tmp = items[j + 1];
                    items[j + 1] = items[j];
                    items[j] = tmp;
                }
            }
        }
    }
}

稳定性: 稳定

时间复杂度O(N^2)

空间复杂度O(1)

第二道题目:

分析: + - * / ( ) 0-9

1+2 (1,2,+) 对1和2进行加操作运算

1+2*3+2 ((1,(2,3,*),+) ,2,+)

1+2*(1-2) (1,(2,(1,2,-),*),+)

采用两个栈(stack),一个栈（dataStack) 存在数值，一个栈(operatorStack)存放操作符号。

关于数值的解析: 从正负号开始||从数字开始，直到遇到操作符结束 || 表达式结束

关于正负号的识别:

第0个字符可以是正负号

-1+1 中的第0个字符是负号

(后可以接正负号

1-(-2-3)中的 数字2前面的字符是负号

即遇到操作符时，前面可能一个数值，我们需要将此数值压入dataStack

遇到操作符号进行的处理:

判断该操作符号是否需要压入栈中

需要压入栈中的情况:

1:operatorStack为空

2:符号本身为(, 或者栈顶元素为(

3:本符号的优先级比栈顶元素的优先级高 (乘除高于加减）

其他的情况:

如果符号为")"

如 （1+2*3） 弹出*号，2和3做乘法， 再弹出+号，1和6做加法，弹出"(" , 结束

另外一种情况：

1+2*3 + 2

* 优先级高于+ 2*3 先计算

+ 优先级高于 + 1+6 先计算

操作栈顶元素的优先级比本符号的优先级高，那么弹出栈顶的操作符

异常情况分析:

1：1(2， 1a2 操作符号不是加减乘除符号)

2: 1++2 +++ 计算时缺数字

3：(1+2 1+2） 括号未正常关闭

4：除数不能为0

5: +++ (++ 会导致解析数字异常

遗憾， 后两种异常未处理。

正常结束 dataStack的size为1， operatorStack的size为0.

import java.util.Stack;

public class ExpressEval {

    public static void main(String[] args) {

        //  -123 + 345 ;

        String test = "9/7/1";
        int result = eval(test);
        System.out.println(result);

    }


    public static int eval(String input) {


        Stack<Integer> dataStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        // assert input 不为空
        char[] items = input.toCharArray();
        int length = items.length;

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < length; i++) {

            char item = items[i];
            if ((item == '+' || item == '-') && (i == 0 || items[i - 1] == '(')) {
                sb.append(item);
            } else if (item <= '9' && item >= '0') {
                sb.append(item);
            } else {

                if (sb.length() > 0) {
                    int number = parseInt(sb);
                    dataStack.push(number);
                    sb = new StringBuilder();
                }


                if (operatorStack.empty()) {
                    if (item == ')') {
                        throw new IllegalArgumentException("非法表达式");
                    }
                    operatorStack.push(item);
                } else {

                    char top = operatorStack.peek();
                    if (item == '(' || top == '(') {
                        operatorStack.push(item);
                    } else if (item == ')') {

                        for (; ; ) {

                            if (operatorStack.empty()) {
                                throw new IllegalArgumentException("非法表达式，未找到与之匹配的(");
                            }

                            char operator = operatorStack.pop();
                            if (operator == '(') {
                                break;
                            }

                            int tmp = cal(dataStack, operator);
                            dataStack.push(tmp);
                        }

                    } else if ((item == '*' || item == '/') && (top == '+' || top == '-')) {
                        operatorStack.push(item);
                    } else {

                        while (!operatorStack.empty()) {

                            top = operatorStack.peek();
                            if (top == '(') {
                                break;
                            }
                            if (youxian(top, item)) {
                                operatorStack.pop();
                                int tmp = cal(dataStack, top);
                                dataStack.push(tmp);
                            } else {
                                break;
                            }
                        }

                        operatorStack.push(item);
                    }
                }
            }
        }


        if (sb.length() > 0) {
            dataStack.push(parseInt(sb));
        }


        while (!operatorStack.empty()) {
            char op = operatorStack.pop();
            int tmp = cal(dataStack, op);
            dataStack.push(tmp);
        }


        if (dataStack.size() != 1 || operatorStack.size() != 0) {
            throw new IllegalArgumentException("非法表达式");
        }

        return dataStack.pop();
    }


    public static boolean youxian(char top, char current) {
        if ((current == '+' || current == '-') || (top == '*' || top == '/')) {
            return true;
        }
        return false;
    }


    public static int cal(Stack<Integer> data, char operator) {

        if (data.size() < 2 || !(operator == '+' || operator == '-' || operator == '*' || operator == '/')) {
            throw new IllegalArgumentException("表达式非法");
        }

        int data2 = data.pop();
        int data1 = data.pop();

        if (operator == '+') {
            return data1 + data2;
        } else if (operator == '-') {
            return data1 - data2;
        } else if (operator == '*') {
            return data1 * data2;
        } else {
            return data1 / data2;
        }

    }


    public static int parseInt(StringBuilder sb) {

        if (sb.length() == 1 && (sb.charAt(0) == '+' || sb.charAt(0) == '-')) {
            throw new IllegalArgumentException("表达式非法");
        }

        try {
            return Integer.parseInt(sb.toString());
        } catch (Exception e) {
            throw new IllegalArgumentException("解析整数抛出了异常");
        }

    }
}