国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Expression Tree Build

qpal / 3521人閱讀

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 (2*6-(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 <= expression.length; i++) {
            if(i != expression.length)
            {
                if (expression[i].equals("(")) {
                    base += 10;
                    continue;
                }
                if (expression[i].equals(")")) {
                    base -= 10;
                    continue;
                }
                val = get(expression[i], base);
            }
            TreeNode right = i == expression.length ? new TreeNode(
                    Integer.MIN_VALUE, "") : new TreeNode(val,
                    expression[i]);
            while (!stack.isEmpty()) {
                if (right.val <= stack.peek().val) {
                    TreeNode nodeNow = stack.pop();
                    if (stack.isEmpty()) {
                        right.root.left = nodeNow.root;
                    } else {
                        TreeNode left = stack.peek();
                        if (left.val < right.val) {
                            right.root.left = nodeNow.root;
                        } else {
                            left.root.right = nodeNow.root;
                        }
                    }
                } else {
                    break;
                }
            }
            stack.push(right);
        }        
        return stack.peek().root.left;
    }
};
class Solution {
public:
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    int getLevel(string opt) {
        if (opt == "(")
            return 0;
        if (opt == "+" || opt == "-")
            return 1;
        if (opt == "*" || opt == "/")
            return 2;
        return 3;
    }
    bool isOperator(string c) {
        return (c == "+" || c == "-" || c == "*" || c == "/");
    }
    
    vector convertToRPN(vector &expression) {
        stack st;
        vector RPN;
        int len = expression.size();
        for (int i = 0; i < len; ++i) {
            string c = expression[i];
            if (c == "(")
                st.push(c);
            else if (c == ")") {
                while (st.top() != "(") {
                    RPN.push_back(st.top());
                    st.pop();
                }
                st.pop();
            } else {
                if (!isOperator(c))
                    st.push(c);
                else {
                    while (!st.empty() && getLevel(st.top()) >= 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 < len; ++i) {
            string s = RPN[i];
            ExpressionTreeNode *pNode = new ExpressionTreeNode(s);
                if (s == "+" || s == "-" || s == "*" || s == "/") {
                    ExpressionTreeNode *pRight = nodeStack.top();
                    nodeStack.pop();
                    ExpressionTreeNode *pLeft = nodeStack.top();
                    nodeStack.pop();

                    pNode->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 < len; ++i) {
            String s = expression[i];
            if (s == "(") stack.push(s);
            else if (s == ")") {
                while (stack.peek() != "(") {
                    deq.add(stack.peek());
                    stack.pop();
                }
                stack.pop();//delete "("
            }
            else {
                if (!isOperator(s)) {
                    stack.push(s);
                }
                else {
                    while (!stack.isEmpty() && getLevel(stack.peek()) >= 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 < len; ++i) {
            String s = deq.get(i);
            ExpressionTreeNode node = new ExpressionTreeNode(s);
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                ExpressionTreeNode nodeRight = stack.peek();
                stack.pop();
                ExpressionTreeNode nodeLeft = stack.peek();
                stack.pop();
                node.right = nodeRight;
                node.left = nodeLeft;
                stack.push(node);
            }
            else stack.push(node);
        }
        if (stack.isEmpty()) return null;
        else return stack.peek();
    }
}
import java.util.*;

public class Solution {
    public ExpressionTreeNode build(String[] expression) {
        Stack 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();
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65024.html

相關文章

  • [LintCode] Segment Tree Build & Segment Tree B

    摘要:唯一需要注意的就是的賦值取左右子樹的的較大值,最后一層的獨立結點的為對應數組中的值。 Segment Tree Build I Problem The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interv...

    honhon 評論0 收藏0
  • [LintCode] Segment Tree Query I & Segment Tree

    摘要:題目是要查詢到這個區間內某一點的。值是從最底層的子節點值里取最大值。因此,不用太復雜,遞歸就可以了。與所不同的是,對所給區間內的元素個數求和,而非篩選。這樣就會出現的情況,視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

    vibiu 評論0 收藏0
  • [LintCode] Interval Minimum Number

    摘要:這道題目是篩選出數組中的最小值,存入新數組。因此,聯想到和系列的題目,對于的處理,使用線段樹是非常有效的方法。之前我們創建的線段樹,有和兩個。參照這個參數,可以考慮在這道題增加一個的參數,代表每個結點的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...

    taowen 評論0 收藏0
  • LintCodeExpression Expand 非遞歸stack完成DFS(String)

    摘要:直接的方法不可取因為是每一層。層直接從取出實際上是將這個后應該得到。這個時候考慮逆向,建立一個,將出來的東西再一個順序,逆逆得順是一個很好用的操作符,判斷一個對象是否是一個類的實例。坑小心一點這種情況啊代碼 這道題真是超級棒的stack DFS樣板題啊,在這里給自己寫個小小的總結 思路:想到stack并不難,這種嵌套式一般是DFS的思想,先走到最里面最小的那個括號,然后逐漸回到上一層→...

    livem 評論0 收藏0
  • 表達式類算法題小結

    摘要:將表達式轉換為逆波蘭式,然后求值轉換中綴表達式為逆波蘭式魯棒性檢測,表達式中沒有操作數計算逆波蘭式值參考 表達式類算法題小結 [TOC] 聲明 文章均為本人技術筆記,轉載請注明出處:[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/ 表達式分類 根據運算符與相關操作操作數的位置不同,將表達式分為前綴,中綴和后綴表...

    Heier 評論0 收藏0

發表評論

0條評論

qpal

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<