测试用例“([}}])”无法验证在 java 中编码的表达式（平衡括号问题）

Question

这段代码是我在尝试解决Leet代码问题时编写的（下面给出了问题的link），它执行了平衡括号但失败了条件（[}}] ) 谁能帮帮我。

谢谢。

问题link---> https://leetcode.com/problems/valid-parentheses/

import java.util.*;

public class expressionValidation 
{
    public static void main(String[] args)
 {
            try (Scanner sc = new Scanner(System.in))/*trying to avoid any kind of exceptions*/
 {
                String str = sc.nextLine();
                String exp = "";/*new string  to modify the given expression*/
                int l = str.length();

                for(int i=0;i<l;i++)
{
                    if(str.charAt(i)=='{'||str.charAt(i)=='('||str.charAt(i)=='['||str.charAt(i)=='}'||str.charAt(i)==']'||str.charAt(i)==')')
{
                        exp+=str.substring(i,i+1);/*newly modified string afterstrong text removing everything except brackets'(' '[' '{' ' }' ']' ')'*/
                    }
                }   
                stack ob = new stack();
                System.out.println(ob.isValid(exp)?"Balanced":"NOT Balanced");
            }
        
    }
}

## The following is the stack class

class stack
{
    boolean isValid(String exp)
{
        int l =exp.length();
         if(l%2!=0)
                return false;
         Stack<Character> st = new Stack<Character>();
         for(int i=0;i<l;i++) 
{
             if(exp.charAt(i)=='{' ||exp.charAt(i)=='(' ||exp.charAt(i)=='[' ) {
                 st.push(exp.charAt(i));
             }
             else if(exp.charAt(i)=='}' && !(st.isEmpty()) && st.peek()=='{') {
                 st.pop();
             }
             else if(exp.charAt(i)==')' && !(st.isEmpty()) && st.peek()=='(') {
                 st.pop();
             }
             else if(exp.charAt(i)==']' && !(st.isEmpty()) && st.peek()=='[') {
                 st.pop();
             }
             String str = st.toString();
             System.out.println(str);
         }
        return st.isEmpty();
    }

}

Answer 1

当遇到}且以下条件不成立时

else if(exp.charAt(i)=='}' && !(st.isEmpty()) && st.peek()=='{') {

你应该已经产生了一个错误，但你只是默默地忽略传入的 } 并继续迭代。所以所有不成对的关闭 parenthesis/brackets 都只是从你的输入中默默地删除。而不是 ([}}]) 你分析 ([]) 这是一个平衡的字符串，所以你没有错误。

其他结束字符也是如此。

Answer 2

试试这个。

boolean isValid(String s) {
    int max = s.length(), index = 0;
    char[] stack = new char[max];
    for (int i = 0; i < max; ++i) {
        char c = s.charAt(i);
        switch (c) {
        case '(': stack[index++] = ')'; break;
        case '[': stack[index++] = ']'; break;
        case '{': stack[index++] = '}'; break;
        default:
            if (index <= 0 || stack[--index] != c)
                return false;
            break;
        }
    }
    return index == 0;
}

Answer 3

我的 LeetCode 提交：-

public boolean isValid(String s) {
    Stack<Character> sc = new Stack<>();
    for(int i =0;i<s.length();i++){
        char ch = s.charAt(i);
        if(ch == '(' || ch == '{' || ch == '['){
            sc.push(ch);
        }else if(ch == ')'){
            if(!sc.isEmpty() && sc.peek() == '('){
                sc.pop();
            }else{
                return false;
            }
        }else if(ch == '}'){
            if(!sc.isEmpty() && sc.peek() == '{'){
                sc.pop();
            }else{
                return false;
            }
        }else if(ch == ']'){
            if(!sc.isEmpty() && sc.peek() == '['){
                sc.pop();
            }else{
                return false;
            }
        }
    }
    if(sc.isEmpty()){
        return true;
    }else{
        return false;
    }
}

测试用例“([}}])”无法验证在 java 中编码的表达式（平衡括号问题）

Fails for the testcase "([}}])" to validate expression(balancing parenthesis problem) which is coded in java

java

stack

data-structures