12、数据结构与算法 - 实战：栈3

题目：
 一个对于一个单行的逆波兰表达式，由如下元素构成：
数字：十进制数字字符构成的正整数，比如 223
运算符：支持三种运算符^+和*，分别代表自增，加法和乘法
分隔符：一个或者多个空格
例如下面的字符串就是个逆波兰表达式
2 3  4 * ^ 5 +
逆波兰表达式在一个基于栈的虚拟机中求解，虚拟机的栈能保存16个整数，虚拟机从左向右扫描表达式，遇到整数就压栈，遇到表达式则从栈顶弹出若干个整数进行计算，计算结果重新压回栈中。
其中运算符^从栈顶弹出一个整数，增加1之后压栈；运算符+和*从栈顶弹出两个整数，分别做相加和相乘运算后压栈。如果遇到运算符的时候，栈内没有足够的整数，称为下溢出，返回-1；
把整数压栈的时候，如果栈没有足够的空间，称为上溢出，返回-2；如果整个计算过程中没有发生溢出，在整个表达式求解完成后，返回栈顶的整数。

说明：该题来自2017阿里巴巴实习笔试编程题，答案是自己写的，如有错误，敬请指正！

public class AlibabaTest {
    public static void main(String[] args) {
        ArrayList<Integer> inputs = new ArrayList<Integer>();
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        if(line != null && !line.isEmpty()) {
            int res = resolve(line.trim());
            System.out.println(String.valueOf(res));
        }
    }

    // write your code here
    public static int resolve(String expr) {

        // 获取字符串集合
        StringTokenizer st = new StringTokenizer(expr);

        // 创建栈来存储操作数
        LinkedListStack<Integer> stack = new LinkedListStack<Integer>();

        // 遍历字符串集合
        while (st.hasMoreTokens()) {
            // 获取一个字符串
            String str = st.nextToken();

            switch (str) {
            case "*":
                // 双目操作需要保证数据栈至少有两个操作数
                if (stack.size() >= 2) {
                    int oper1 = stack.pop();
                    int oper2 = stack.pop();
                    stack.push(oper1 * oper2);
                } else {
                    // 栈内没有足够的整数，称为下溢出，返回-1
                    return -1;
                }
                break;
            case "+":
                // 双目操作需要保证数据栈至少有两个操作数
                if (stack.size() >= 2) {
                    int oper1 = stack.pop();
                    int oper2 = stack.pop();
                    stack.push(oper1 + oper2);
                } else {
                    // 栈内没有足够的整数，称为下溢出，返回-1
                    return -1;
                }
                break;
            case "^":
                if (!stack.isEmpty()) {
                    int oper = stack.pop();
                    oper += 1;
                    stack.push(oper);
                } else {
                    // 栈内没有足够的整数，称为下溢出，返回-1
                    return -1;
                }
                break;
            default:
                // 如果是操作数，直接入栈
                stack.push(Integer.valueOf(str));
                break;
            }
        }
        // 返回栈顶元素
        return stack.pop();

    }
}

题目：如何用栈只扫描一次就能计算中缀表达式的值？
思路：
1.创建一个空的操作数栈
2.创建一个空的操作符栈
3.遍历每一个字符，并根据情况处理
  如果是数字则直接压入操作数栈
  如果是操作符则判断优先级，并进行处理
  如果是"("直接压入操作符栈
  如果是")"，则从操作符栈中弹出运算符，直到"("出栈；但"("不输出
4.要保证操作数栈和操作符栈为空

/**
 * 计算中缀表达式结果
 * @param infix 中缀表达式
 * @return 运算结果
 */
public static int resultOfInfix(String infix) {
    // 1.获取字符串集合
    StringTokenizer st = new StringTokenizer(infix);

    // 2.1 创建栈来存储操作数
    LinkedListStack<Integer> datas = new LinkedListStack<Integer>();

    // 2.2 创建栈来存储操作符
    LinkedListStack<String> opers = new LinkedListStack<String>();

    // 标记运算符优先级
    boolean priority = false;

    // 3.遍历字符串集合
    while (st.hasMoreTokens()) {
        // 3.1 获取下一个字符串
        String str = st.nextToken();
        boolean flag = false;
        // 3.2 检查字符串
        switch (str) {
        case "(":
        case "+":
        case "-":
        case "*":
        case "/":
            break;
        // 遇到")"时，从栈中弹出运算符，直到"("出栈；但"("不输出
        case ")":
            while (!opers.top().equals("(")) {
                calculate(datas, opers);
            }
            // 将"("弹出
            opers.pop();
            flag = true;
            break;
        default:
            // 如果是操作数则压入数据栈
            datas.push(Integer.valueOf(str));
            flag = true;
            break;
        }

        // 3.3 如果对")"和操作数做过处理，则结束当前循环，继续读取下一个字符串
        if (flag) {
            continue;
        }

        // 3.4 操作符栈不为空，则判断运算符优先级
        if (!opers.isEmpty()) {
            priority = compare(opers.top().toCharArray()[0], str.toCharArray()[0]);
            // 栈内运算符优先级高
            if (priority) {
                calculate(datas, opers);
            }
        }

        // 3.5 运算符入栈
        opers.push(str);
    }

    // 4.操作符栈不为空，说明存在数据未处理
    while (!opers.isEmpty()) {
        calculate(datas, opers);
    }

    // 5.返回运算结果
    return datas.pop();
}

/**
 * 运算
 * @param datas 数据栈
 * @param opers 操作符栈
 */
public static void calculate(LinkedListStack<Integer> datas, LinkedListStack<String> opers) {
    int oper1 = datas.pop();
    int oper2 = datas.pop();
    switch (opers.pop()) {
    case "*":
        datas.push(oper2 * oper1);
        break;
    case "/":
        datas.push(oper2 / oper1);
        break;
    case "+":
        datas.push(oper2 + oper1);
        break;
    case "-":
        datas.push(oper2 - oper1);
        break;
    default:
        break;
    }
}

测试代码如下：

public static void main(String[] args) {
    System.out.println("--------------------");
    String string = "( 1 + 2 ) * ( 5 - 3 )";
    int result = resultOfInfix(string);
    // 结果为6
    System.out.println(result);
}