栈应用两则

一、非递归先序遍历二叉树

算法的基本思想：

1. 将根节点压入栈
2. 取出栈顶元素，若右子树不为空，右子树入栈，若左子树不为空，左子树入栈
3. 执行步骤2直到栈为空

public class Traversal {
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();

        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            list.add(cur.getVal());
            if (cur.getRight() != null) {
                stack.add(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.add(cur.getLeft());
            }

        }
        return list;
    }

}

二、表达式求值

任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)构成，我们把运算符和界限符统称为算符，它们构成的集合定义为OP，算符间的优先级关系如下表所示：

	+	-	*	/	（	）	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
#	<	<	<	<	<		=

“（”和”）”的关系为相等，表示当左右括号相遇时候，括号内的运算已经完成，同理，当两个”#”相遇时表示整个表达式求值完毕。”）”与”（”、”#”与”）”和”（”与”#”之间无对应优先关系，因为其不合法。

定义两个栈，其中一个存放运算符，另一个存放操作数或计算的结果。

算法基本思想为：

1. 初始化操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2. 依次读入表达式的每个字符，若为操作数则进入操作数栈，如是运算符则和运算符栈的栈定元素进行比较，这里有三种情况：
   1. 栈顶元素优先权低：直接将操作符入栈，读入下一个字符
   2. 两操作符优先权相等：脱括号，读入下一个字符
   3. 栈顶元素优先权高：腿栈计算结果，并将计算结果入操作数栈
3. 继续读入直到表达式求值完毕，即运算符栈的栈顶元素和当前读入的字符均为”#”

代码实现如下：

public class Express {

    public static Map<String, Map<String, String >> relationship = new HashMap<>();
    private Stack<String> optr = new Stack<>(); //运算符栈
    private Stack<String> opnd = new Stack<>(); //运算数栈
    private Iterator iterator;

    public Express(String s) {
        String[] split = s.split(" ");
        List<String> list = new ArrayList<>(Arrays.asList(split));
        System.out.println(list);
        this.iterator = list.iterator();

        Map<String, String> map1 = new HashMap<String, String>(){
            {
                put("+", ">");
                put("-", ">");
                put("*", "<");
                put("/", "<");
                put("(", "<");
                put(")", ">");
                put("#", ">");
            }
        };
        relationship.put("+", map1);
        Map<String, String> map2 = new HashMap<String, String>(){
            {
                put("+", ">");
                put("-", ">");
                put("*", "<");
                put("/", "<");
                put("(", "<");
                put(")", ">");
                put("#", ">");
            }
        };
        relationship.put("-", map2);
        Map<String, String> map3 = new HashMap<String, String>(){
            {
                put("+", ">");
                put("-", ">");
                put("*", ">");
                put("/", ">");
                put("(", "<");
                put(")", ">");
                put("#", ">");
            }
        };
        relationship.put("*", map3);
        Map<String, String> map4 = new HashMap<String, String>(){
            {
                put("+", ">");
                put("-", ">");
                put("*", ">");
                put("/", ">");
                put("(", "<");
                put(")", ">");
                put("#", ">");
            }
        };
        relationship.put("/", map4);
        Map<String, String> map5 = new HashMap<String, String>(){
            {
                put("+", "<");
                put("-", "<");
                put("*", "<");
                put("/", "<");
                put("(", "<");
                put(")", "=");
                put("#", "");
            }
        };
        relationship.put("(", map5);
        Map<String, String> map6 = new HashMap<String, String>(){
            {
                put("+", ">");
                put("-", ">");
                put("*", ">");
                put("/", ">");
                put("(", "");
                put(")", ">");
                put("#", ">");
            }
        };
        relationship.put(")", map6);
        Map<String, String> map7 = new HashMap<String, String>(){
            {
                put("+", "<");
                put("-", "<");
                put("*", "<");
                put("/", "<");
                put("(", "<");
                put(")", "");
                put("#", "=");
            }
        };
        relationship.put("#", map7);

        optr.add("#");
    }

    // 判断是否是运算符
    public boolean isOps (String c) {
        return c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/") || c.equals("#")
                || c.equals("(") || c.equals(")");
    }

    public int operate(String a, String opt, String b) {
        switch (opt){
            case "+":
                return Integer.parseInt(a) + Integer.parseInt(b);
            case "-":
                return Integer.parseInt(b) - Integer.parseInt(a);
            case "*":
                return Integer.parseInt(a) * Integer.parseInt(b);
            case "/":
                return Integer.parseInt(b) / Integer.parseInt(a);
            default:
                throw new ValueException("Oops...");
        }

    }

    //读取一个字符
    public String getChar() {

        if (iterator.hasNext()){
            return (String) iterator.next();
        }
        return "#";
    }

    public String precede(String s, String c) {
        return relationship.get(s).get(c);
    }

    public int parser () {
        String c = getChar();
        while (!c.equals("#") || !optr.peek().equals("#")) {
            if (! isOps(c)) {
                opnd.add(c);
                c = getChar();
            }else {
                switch (precede(optr.peek(), c)) {
                    case "<":
                        optr.add(c);
                        c = getChar();
                        break;
                    case "=":
                        optr.pop();
                        c = getChar();
                        break;
                    case ">":
                        String op = optr.pop();
                        String a = opnd.pop();
                        String b = opnd.pop();
                        opnd.add(Integer.toString(operate(a, op, b)));
                        break;
                }
            }
        }

        return Integer.parseInt(opnd.peek());
    }

    public static void main(String[] args) {
        Express exp = new Express("5 * ( 10 + 2 )");
        System.out.println(exp.parser());
    }

}