H

1526882596

tags: Stack, Math, Expression Tree, Binary Tree, Minimum Binary Tree

给一个expression String, 要evaluate这个expression的值.

Expression string 里面包括 +, -, 整数, 开合括号, 还有space.

#### Expression Tree

- Expression Tree是一个 weight-based的 min-tree

- 基于 运算符号 + 数字的 tree: 数字永远在leaf, 然后符号是tree node, 括号不出现在tree里面

- 用 monotonuous stack 来构建这个tree

##### Thinking points

- Understand Expression Tree

- Use stack to build the expression tree + understand the weight system

- Use post-order traversal to evaluate the tree

- 注意, input里面的数字不会是single digit, 所以需要一个buffer存number string

- 整个题目的做法, 可以参照 `Expression Evaluation`

```

/*

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ),

the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

*/

/*

build expression tree to evaluate expression

two functions:

1. build tree

parse string

skip space

identify operator

calculate weight of operator

add parentheses to base weight

2. evaluate with post-order traversal

*/

class Solution {

class TreeNode {

int weight;

String str;

TreeNode left, right;

public TreeNode(int weight, String str) {

this.weight = weight;

this.str = str;

}

}

public int calculate(String s) {

if (s == null || s.length() == 0) return 0;

TreeNode root = buildTree(s); // build expression tree

return (int)evaluate(root); // post-order traversal of the tree

}

// build tree based on input string, min-tree. return root

private TreeNode buildTree(String s) {

int n = s.length();

char[] chars = s.trim().toCharArray();

Stack<TreeNode> stack = new Stack<>();

int base = 0;

StringBuffer sb = new StringBuffer();

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

char c = chars[i];

if (c == ' ') {

continue;

} else if (c == '(') { // '()' are used to add weight, not stored in tree

base = getWeight(base, c);

continue;

} else if (c == ')') {

base = getWeight(base, c);

continue;

} else if (i < n - 1 && isDigit(chars[i]) && isDigit(chars[i + 1])) { // continue to get remaining of the int

sb.append(c);

continue;

}

String str;

if (isDigit(c)) {

sb.append(c);

str = sb.toString();

sb.setLength(0); // clean up

} else {

str = c + "";

}

// use monotonuous stack to build min-tree

TreeNode node = new TreeNode(getWeight(base, c), str);

while (!stack.isEmpty() && node.weight <= stack.peek().weight) {

node.left = stack.pop();

}

if (!stack.isEmpty()) {

stack.peek().right = node;

}

stack.push(node);

}

TreeNode root = null;

while (!stack.isEmpty()) {

root = stack.pop();

}

return root; // it's the root of tree, always a operator

}

// post-order traversal to evaluate the expression

private long evaluate(TreeNode root) {

if (root == null) return 0;

long left = evaluate(root.left);

long right = evaluate(root.right);

long result = 0;

switch(root.str) {

case "+":

result = left + right;

break;

case "-":

result = left - right;

break;

case "*":

result = left * right;

break;

case "/":

result = left / right;

break;

default:

result = Long.parseLong(root.str);

}

return result;

}

// get weight of the character. integer weights the most and will be leaf.

// Remember to store the result using long

private int getWeight(int base, char c) {

if (c == '(') return base + 10;

if (c == ')') return base - 10;

if (c == '+' || c == '-') return base + 1;

if (c == '*' || c == '/') return base + 2;

return Integer.MAX_VALUE;

}

private boolean isDigit(char c) {

return c >= '0' && c <= '9';

}

}

```