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 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';
}
}
```