匹配括号使用栈

huangapple
未分类评论43阅读模式
英文:

Matching Parantheses using stack

问题

以下代码是使用堆栈来检查给定的字符串是否有平衡的括号。

对于输入“[]”，得到了错误的输出。它应该打印出true，但我得到的结果是false。

import java.util.*;
class Solution {
    public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack<Character> st = new Stack<>();
        boolean flag = true;
        while (sc.hasNext()) {
            String input = sc.next();
            // 完成代码
            for (int i = 0; i < input.length(); i++) {
                flag = false;
                if ((input.charAt(i) == '{') || (input.charAt(i) == '(') || (input.charAt(i) == '[')) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == '}') || (input.charAt(i) == ')') || (input.charAt(i) == ']')) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = st.pop();
                        if ((item == '(') && (input.charAt(i) == ')'))
                            flag = true;
                        if ((item == '{') && (input.charAt(i) == '}'))
                            flag = true;
                        if ((item == '[') && (input.charAt(i) == ']'))
                            flag = true;
                    }
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}
英文:

Below code is to check whether the given string has balanced parantheses or not using stack.
Getting wrong output for input "[]". It should print true but the result that i am getting is false.

import java.util.*;
class Solution{
	public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack st = new Stack();
        boolean flag = true;
        while (sc.hasNext()) {
            String input = sc.next();
            //Complete the code
            for (int i = 0; i &lt; input.length(); i++) {
                flag = false;
                if ((input.charAt(i) == &#39;{&#39;) || (input.charAt(i) == &#39;(&#39;) || (input.charAt(i) == &#39;[&#39;)) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == &#39;}&#39;) || (input.charAt(i) == &#39;)&#39;) || (input.charAt(i) == &#39;]&#39;)) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = (char) st.pop();
                        if ((item == &#39;(&#39;) &amp;&amp; (input.charAt(i) == &#39;)&#39;))
                            flag = true;
                        if ((item == &#39;{&#39;) &amp;&amp; (input.charAt(i) == &#39;}&#39;))
                            flag = true;
                        if ((item == &#39;[&#39;) &amp;&amp; (input.charAt(i) == &#39;]&#39;))
                            flag = true;
                    }
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}

答案1

得分: 0

我已经按照您的要求翻译了您提供的内容，以下是翻译好的部分：

我已经在下面的代码中进行了一些更改（由注释标识），这些更改应该使其正常工作。

import java.util.*;
class Solution{
    public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack st = new Stack();
        while (sc.hasNext()) {
            // jim - 将此部分移到循环内。
            // 假设输入是好的，除非证明相反。
            boolean flag = true;
            String input = sc.next();
            // 完成代码
            // jim - 添加了&quot;&amp;&amp; flag == true&quot;，以便在输入有问题时退出循环
            for (int i = 0; i &lt; input.length() &amp;&amp; flag == true; i++) {
                // jim - 将此部分注释掉。我们将假设它是好的。如果发现输入有问题，我们设置标志，
                // 上面的&quot;&amp;&amp; flag == true&quot;条件将退出循环。
                // flag = false; 
                if ((input.charAt(i) == &#39;{&#39;) || (input.charAt(i) == &#39;(&#39;) || (input.charAt(i) == &#39;[&#39;)) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == &#39;}&#39;) || (input.charAt(i) == &#39;)&#39;) || (input.charAt(i) == &#39;]&#39;)) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = (char) st.pop();
                        // jim - 在这里，检查是否不相等，并设置为false。
                        if ((item == &#39;(&#39;) &amp;&amp; (input.charAt(i) != &#39;)&#39;))
                            flag = false;
                        if ((item == &#39;{&#39;) &amp;&amp; (input.charAt(i) != &#39;}&#39;))
                            flag = false;
                        if ((item == &#39;[&#39;) &amp;&amp; (input.charAt(i) != &#39;]&#39;))
                            flag = false;
                    }
                }
                else {
                    // jim - 添加了这个&#39;else&#39;子句。
                    // 如果除了[{()}]之外还有任何其他字符，那么输入就是错误的。
                    flag = false;
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}

您的代码还有一些可以改进的地方，但我记录的那些更改应该足以使其正常工作。
英文:

I have reproduced your code below with a few changes (identified by comments) that should get it to work.

import java.util.*;
class Solution{
    public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack st = new Stack();
        while (sc.hasNext()) {
            // jim - Moved this to inside the loop.
            // Assume the input is good unless proven otherwise.
            boolean flag = true;
            String input = sc.next();
            //Complete the code
            // jim - Added the &quot;&amp;&amp; flag == true&quot; to exit if the input is bad
            for (int i = 0; i &lt; input.length() &amp;&amp; flag == true; i++) {
                // jim - Commented this out. We&#39;ll assume it&#39;s good. If the input
                // is found to be bad, we set the flag, and the
                // &quot;&amp;&amp; flag == true&quot; condition above will exit the loop.
                // flag = false; 
                if ((input.charAt(i) == &#39;{&#39;) || (input.charAt(i) == &#39;(&#39;) || (input.charAt(i) == &#39;[&#39;)) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == &#39;}&#39;) || (input.charAt(i) == &#39;)&#39;) || (input.charAt(i) == &#39;]&#39;)) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = (char) st.pop();
                        // jim - here, check for not equal, and set to false.
                        if ((item == &#39;(&#39;) &amp;&amp; (input.charAt(i) != &#39;)&#39;))
                            flag = false;
                        if ((item == &#39;{&#39;) &amp;&amp; (input.charAt(i) != &#39;}&#39;))
                            flag = false;
                        if ((item == &#39;[&#39;) &amp;&amp; (input.charAt(i) != &#39;]&#39;))
                            flag = false;
                    }
                }
                else {
                    // jim - added this &#39;else&#39; clause.
                    // If there&#39;s any character other than [{()}], then it&#39;s
                    // bad input.
                    flag = false;
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}

There are some improvements you could make to your code, but those few changes I documented should get it to work.

huangapple
  • 本文由 发表于 2020年4月4日 03:14:44
  • 转载请务必保留本文链接：https://java.coder-hub.com/61018948.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定