LeetCode-algorithms20:Valid Parentheses

发表于   |   更新于 | | 阅读数
字数统计 653 字 | 阅读时长 4 分钟

LeetCode-algorithms20:Valid Parentheses

Problem:

  • Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
  • An input string is valid if:

    • Open brackets must be closed by the same type of brackets.

    • Open brackets must be closed in the correct order.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

static class ArrayStack{

    //the stack based on array
    private String[] items;
    private int length;
    private int size = 0;

    ArrayStack(int length) {
        this.length = length;
        this.items = new String[length];
    }

    ArrayStack(){
        this.length = 8;
        this.items = new String[length];
    }

    //push
    public boolean push(String item) {
        boolean flag = false;
        if (size < length) {
            items[size] = item;
            size++;
            flag = true;
        }
        return flag;
    }
    //pop
    public String pop() {
        String result = "";
        if (size > 0) {
            result = items[size - 1];
            size = size - 1;
        }
        return result;
    }

    public String getTop(){
        return this.items[size-1];
    }

    private  boolean sizeCheck(){
        if(null == this.items || length == 0){
            return false;
        }
        return true;
    }
    
}


// the method to justice Valid Parentheses
public static boolean isUsefulBrakes(String str) {
    
    int midLength = str.length() / 2;
    ArrayStack stackLeft = new ArrayStack(str.length());
    ArrayStack stackRight = new ArrayStack(midLength);

    String lit = "()";
    String mid = "[]";
    String big = "{}";
    String litL = "(";
    String litR = ")";
    String midL = "[";
    String midR = "]";
    String bigL = "{";
    String bigR = "}";

    String lk = "([{";
    String rk = ")]}";

    String[] brakeArray = str.split("");
    for (int i = 0; i < str.length(); i++) {
        if (StringUtils.isNotBlank(brakeArray[i])) {
            stackLeft.push(brakeArray[i]);
        }
    }
	//the odd number length can`t be true 
    if (stackLeft.size() % 2 == 1) {
        return false;
    }
    
    //start to pop 
    while (stackLeft.size > 0) {
        //if the right stack`s size equals to the left stack,which means all the brackets int right stack is right brackets
        if(stackLeft.size==stackRight.size){
            while(stackLeft.size > 0){
                String ltop = stackLeft.pop();
                String rtop = stackRight.pop();
                //the same to the left stack
                if(rk.indexOf(ltop)>0){
                    return false;
                }
			  //if the same brackets type 
                if(lit.indexOf(ltop)>-1 && lit.indexOf(rtop)>-1){
                    continue;
                }else if(mid.indexOf(ltop)>-1 && mid.indexOf(rtop)>-1){
                    continue;
                }else if(big.indexOf(ltop)>-1 && big.indexOf(rtop)>-1){
                    continue;
                }
                return false;
            }
        }
        String top1 = stackLeft.pop();
        String top2 = stackLeft.pop();

        //the first element of left stakc must be a right brackets
        if(lk.indexOf(top1)>-1 && stackRight.size >0){
            // if not , compare with the top of the right stack
            String rtop = stackRight.pop();
            // is they the same type and match eacher other
            if(top1.equals(litL) && rtop.equals(litR)){
                // push top2 back to the left stack
                stackLeft.push(top2);
                continue;
            }else if(top1.equals(midL) && rtop.equals(midR)){
                stackLeft.push(top2);
                continue;
            }else if(top1.equals(bigL) && rtop.equals(bigR)){
                stackLeft.push(top2);
                continue;
            }
            return false;
        }else if(rk.indexOf(top1)>-1){
            if(rk.indexOf(top2)>-1){
                //the first two element are all right brackets ,push into the right stack
                stackRight.push(top1);
                stackRight.push(top2);
            }else if(lk.indexOf(top2)>-1){
                //which means the top2 must be the same type of the left brackets 
                if(lit.indexOf(top1) >-1 && lit.indexOf(top2)>-1){
                    continue;
                }else if(mid.indexOf(top1) >-1 && mid.indexOf(top2)>-1){
                    continue;
                }else if(big.indexOf(top1) >-1 && big.indexOf(top2)>-1){
                    continue;
                }
                return false;
            }
        }
    }
    return true;
}
  • the test input ： {} ，([])，{[()]} , all the result was true
  • TODO ：
    • it seems there some duplicated code should be include into a method ;
    • it`s hard to read so i do think there got a better solution for this probleam ;