[LintCode] Epression Tree Build
Problem
The structure of Expression Tree is a binary tree to evaluate certain expressions.
All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.
Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.
Clarification
See wiki:
Expression Tree
Example
For the expression (26-(23+7)/(1+2)) (which can be represented by ["2" "" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]).
The expression tree will be like
[ - ] / \ [ * ] [ / ] / \ / \[ 2 ] [ 6 ] [ + ] [ + ] / \ / \ [ 23 ][ 7 ] [ 1 ] [ 2 ] .After building the tree, you just need to return root node [-].
Note
Solution
class TreeNode { public int val; public String s; public ExpressionTreeNode root; public TreeNode(int val, String ss) { this.val = val; this.root = new ExpressionTreeNode(ss); }}public class Solution { int get(String a, Integer base) { if (a.equals("+") || a.equals("-")) return 1 + base; if (a.equals("*") || a.equals("/")) return 2 + base; return Integer.MAX_VALUE; } public ExpressionTreeNode build(String[] expression) { // write your code here Stack stack = new Stack(); TreeNode root = null; int val = 0; Integer base = 0; for (int i = 0; i convertToRPN(vector &expression) { stack st; vector RPN; int len = expression.size(); for (int i = 0; i = getLevel(c)) { RPN.push_back(st.top()); st.pop(); } st.push(c); } } } while (! st.empty()) { RPN.push_back(st.top()); st.pop(); } return RPN; } ExpressionTreeNode* build(vector &expression) { // write your code here vector RPN = convertToRPN(expression); int len = RPN.size(); stack nodeStack; for (int i = 0; i right = pRight; pNode->left = pLeft; nodeStack.push(pNode); } else nodeStack.push(pNode); } if (nodeStack.empty()) return NULL; else return nodeStack.top(); }};public class Solution { public boolean isOperator(String s) { return s == "+" || s == "-" || s == "*" || s == "/"; } public int getLevel(String s) { if (s == "(") return 0; if (s == "+" || s == "-") return 1; if (s == "*" || s == "/") return 2; return 3; } public ArrayList convert(String[] expression) { Stack stack = new Stack(); ArrayList deq = new ArrayList(); int len = expression.length; for (int i = 0; i = getLevel(s)) { deq.add(stack.peek()); stack.pop(); } stack.push(s); } } } while (!stack.isEmpty()) { deq.add(stack.peek()); stack.pop(); } return deq; } public ExpressionTreeNode build(String[] expression) { ArrayList deq = convert(expression); System.out.println(deq); int len = deq.size(); Stack stack = new Stack(); for (int i = 0; i op = new Stack(); Stack data = new Stack(); for(int i=0;i='0')){ //System.out.println("get op "+ tmp); switch(firstc){ case '(': ExpressionTreeNode node = new ExpressionTreeNode(tmp); op.push(node); break; case '+': case '-': while(!op.isEmpty()&&op.peek().symbol.charAt(0)!='('){ ExpressionTreeNode opnode = op.pop(); ExpressionTreeNode data1 = data.pop(); ExpressionTreeNode data2 = data.pop(); opnode.left = data2; opnode.right = data1; data.push(opnode); } ExpressionTreeNode node2 = new ExpressionTreeNode(tmp); op.push(node2); break; case '*': case '/': while(!op.isEmpty()&&(op.peek().symbol.charAt(0)=='*'||op.peek().symbol.charAt(0)=='/')){ ExpressionTreeNode opnode = op.pop(); ExpressionTreeNode data1 = data.pop(); ExpressionTreeNode data2 = data.pop(); opnode.left = data2; opnode.right = data1; data.push(opnode); } ExpressionTreeNode node3 = new ExpressionTreeNode(tmp); op.push(node3); break; case ')': while(op.peek().symbol.charAt(0)!='('){ ExpressionTreeNode opnode = op.pop(); ExpressionTreeNode data1 = data.pop(); ExpressionTreeNode data2 = data.pop(); opnode.left = data2; opnode.right = data1; data.push(opnode); } op.pop(); } }else{ //System.out.println("add data "+tmp); ExpressionTreeNode data1 = new ExpressionTreeNode(tmp); data.push(data1); } } while(!op.isEmpty()){ ExpressionTreeNode opnode = op.pop(); ExpressionTreeNode data1 = data.pop(); ExpressionTreeNode data2 = data.pop(); opnode.left = data2; opnode.right = data1; data.push(opnode); } if(data.isEmpty()) return null; return data.pop(); }}关键字：java, stack
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！