Java平衡表达式检查 {[()]}

Question

Java平衡表达式检查 {[()]}

25

我正在尝试创建一个程序，它以字符串作为参数传递给其构造函数。我需要一个方法来检查字符串是否为平衡的括号表达式。它需要处理 ( { [ ] } ) 中的每个开放符号都需要与其对应的闭合括号配对。例如，用户可以输入 [({})] 这将是平衡的，而 }{ 将是不平衡的。这不需要处理字母或数字。我需要使用栈来完成这个操作。

我得到了这个伪代码，但不知道如何在Java中实现它。任何建议都会很棒。

更新- 抱歉忘记发布我已经做的部分。一开始我使用char，然后我尝试过数组 ... 我不确定该怎么办。

import java.util.*;

public class Expression
{
  Scanner in = new Scanner(System.in);
  Stack<Integer> stack = new Stack<Integer>();



  public boolean check()
  {
    System.out.println("Please enter your expression.");
    String newExp = in.next();
    String[] exp = new String[newExp];
    for (int i = 0; i < size; i++)
    { 


      char ch = exp.charAt(i);
      if (ch == '(' || ch == '[' || ch == '{')
        stack.push(i);
      else if (ch == ')'|| ch == ']' || ch == '}')
      {
        //nothing to match with
        if(stack.isEmpty())
        {  
          return false;
        }
        else if(stack.pop() != ch)
        { 
          return false;
        } 

      }            
    }
    if (stack.isEmpty())
    {
      return true;
    }
    else
    {
      return false;
    }
  }


}

- Jess Anastasio

1

伪代码算法看起来很准确，为什么不把你目前的实现发出来呢？ - Jeff Ward

抱歉有些严厉，但你甚至都有伪代码，必须将其翻译成Java。或者至少试一试，自己尝试失败...也许，如果你的问题中有任何努力的迹象 - 如[FAQ]中所述的那样 - 将有助于获得一些帮助，而不是一些陈旧的愤世嫉俗... void main(String[] args...) { //在此处编写代码 }; - ppeterka

我发布了我迄今为止所做的工作，我忘记在开始时发布，非常感谢。 - Jess Anastasio

1

你可以先将循环的索引推入栈中，然后尝试弹出一个字符。你应该使用一个字符栈，并将开放括号推入其中。当你找到一个闭合括号时，弹出栈顶元素并检查它是否正确匹配开放括号，然后继续执行。如果在最后栈为空，则字符串是平衡的。 - Neurax

查看此链接，您将获得更好的理解：http://codereview.stackexchange.com/questions/45916/check-for-balanced-parentheses - pratik deshai

37个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Max.Futerman · Answer 1

///check Parenthesis
public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()){
        if(map.containsKey(c)){
            stack.push(c);
        } else if(!stack.empty() && map.get(stack.peek())==c){
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.empty();
}

- Deepak Ghariyav · Answer 2

package Stack;

import java.util.Stack;

public class BalancingParenthesis {

 boolean isBalanced(String s) {

    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {

        if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {

            stack.push(s.charAt(i)); // push to the stack

        }

        if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {

            if (stack.isEmpty()) {
                return false; // return false as there is nothing to match
            }

            Character top = stack.pop(); // to get the top element in the stack

            if (top == '(' && s.charAt(i) != ')' || top == '{' && s.charAt(i) != '}'
                    || top == '[' && s.charAt(i) != ']') {

                return false;
            }

        }

    }

    if (stack.isEmpty()) {
        return true; // check if every symbol is matched
    }

    return false; // if some symbols were unmatched
}

public static void main(String[] args) {

    BalancingParenthesis obj = new BalancingParenthesis();

    System.out.println(obj.isBalanced("()[]{}[][]"));

}

}

// Time Complexity : O(n)

- Abhishek Chandrashekhar · Answer 3

public class StackProb {

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    List<Boolean> list = new ArrayList<>();

    while (sc.hasNextLine()) {
        String s=sc.nextLine();
        if(!s.isEmpty()) {
            list.add(isBalanced(s));
            //System.out.println(isBalanced(s));
        }else {
            sc.close();
            break;
        }
    }

    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i) + " ");
    }

}

private static boolean isBalanced(String s) {
    boolean res = false;
    Stack<Character> stack = new Stack();
    int countA = 0;
    int countB = 0;
    for (int i = 0; i < s.length(); i++) {

        if(s.charAt(i)=='{' || s.charAt(i)=='(' || s.charAt(i)=='[') {

            stack.push(s.charAt(i));
            countA++;
        }


        if(s.charAt(i)=='}' || s.charAt(i)==')' || s.charAt(i)==']') {

            stack.push(s.charAt(i));
            countB++;
        }

        if(stack.firstElement()=='}' || stack.firstElement()==')' || stack.firstElement()==']') {
            countB++;
        }


    }
    if(countA==countB) {
        return true;
    }
    return false;

}

}

- Himansu Meher · Answer 4

public static void main(String[] args) {
    System.out.println("is balanced : "+isBalanced("(){}[]<>"));
    System.out.println("is balanced : "+isBalanced("({})[]<>"));
    System.out.println("is balanced : "+isBalanced("({[]})<>"));
    System.out.println("is balanced : "+isBalanced("({[<>]})"));
    System.out.println("is balanced : "+isBalanced("({})[<>]"));


    System.out.println("is balanced : "+isBalanced("({[}])[<>]"));
    System.out.println("is balanced : "+isBalanced("([{})]"));
    System.out.println("is balanced : "+isBalanced("[({}])"));
    System.out.println("is balanced : "+isBalanced("[(<{>})]"));

    System.out.println("is balanced : "+isBalanced("["));
    System.out.println("is balanced : "+isBalanced("]"));

    System.out.println("is balanced : "+isBalanced("asdlsa"));
}

private static boolean isBalanced(String brackets){
    char[] bracketsArray = brackets.toCharArray();
    Stack<Character> stack = new Stack<Character>();
    Map<Character, Character> openingClosingMap = initOpeningClosingMap();

    for (char bracket : bracketsArray) {
        if(openingClosingMap.keySet().contains(bracket)){ 
            stack.push(bracket);
        }else if(openingClosingMap.values().contains(bracket)){
            if(stack.isEmpty() || openingClosingMap.get(stack.pop())!=bracket){
                return false;
            }
        }else{
            System.out.println("Only  < > ( ) { } [ ] brackets  are allowed .");
            return false;
        }
    }
    return stack.isEmpty();
}

private static Map<Character, Character> initOpeningClosingMap() {
    Map<Character, Character> openingClosingMap = new HashMap<Character, Character>();
    openingClosingMap.put(Character.valueOf('('), Character.valueOf(')'));
    openingClosingMap.put(Character.valueOf('{'), Character.valueOf('}'));
    openingClosingMap.put(Character.valueOf('['), Character.valueOf(']'));
    openingClosingMap.put(Character.valueOf('<'), Character.valueOf('>'));
    return openingClosingMap;
}

简化和提高可读性。只使用一个地图和最少的条件来获得所需的结果。

- palslav · Answer 5

这个怎么样，它同时使用了栈和计数器检查的概念：

import java.util.*;
class Solution{

public static void main(String []argh)
{
   Scanner sc = new Scanner(System.in);
   while (sc.hasNext()) {
      String input=sc.next();
      Stack<Character> stk = new Stack<Character>();
      char[] chr = input.toCharArray();
      int ctrl = 0, ctrr = 0;
      if(input.length()==0){
          System.out.println("true");
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='{'||chr[i]=='('||chr[i]=='['){
              ctrl++;
              stk.push(chr[i]);
              //System.out.println(stk);
          }
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='}'||chr[i]==')'||chr[i]==']'){
              ctrr++;
              if(!stk.isEmpty())
                  stk.pop();
              //System.out.println(stk);
          }
      }
      //System.out.println(stk);
      if(stk.isEmpty()&&ctrl==ctrr)
        System.out.println("true");
      else
        System.out.println("false");
      }
   }
}

- Nik · Answer 6

import java.util.Stack;

        public class StackParenthesisImplementation {
            public static void main(String[] args) {
                String Parenthesis = "[({})]";
                char[] charParenthesis  = Parenthesis.toCharArray();
                boolean evalParanthesisValue = evalParanthesis(charParenthesis);
                if(evalParanthesisValue == true)
                    System.out.println("Brackets are good");
                else
                    System.out.println("Brackets are not good");
            }
            static boolean evalParanthesis(char[] brackets)
            {       
                boolean IsBracesOk = false;
                boolean PairCount = false;
                Stack<Character> stack = new Stack<Character>();
                for(char brace : brackets)
                {                       
                    if(brace == '(' || brace == '{' || brace == '['){
                        stack.push(brace);  
                        PairCount = false;
                    }
                    else if(!stack.isEmpty())
                    {
                        if(brace == ')' || brace == '}' || brace == ']')
                        {
                            char CharPop = stack.pop();
                            if((brace == ')' && CharPop == '('))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else if((brace == '}') && (CharPop == '{'))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else if((brace == ']') && (CharPop == '['))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else 
                            {
                                IsBracesOk = false;
                                PairCount = false;
                                break;
                            }
                        }   
                    }
                }   
                if(PairCount == false)
                return IsBracesOk = false;
                else
                    return IsBracesOk = true;
            }
        }

- Faizan · Answer 7

**// balanced parentheses problem (By fabboys)**
#include <iostream>
#include <string.h>

using namespace std;

class Stack{

char *arr;
int size;
int top;

public:

Stack(int s)
{
  size = s;
  arr = new char[size];
  top = -1;
}

bool isEmpty()
{
  if(top == -1)
    return true;
 else
    return false;
 }

 bool isFull()
 {
  if(top == size-1)
    return true;
 else
    return false;
 }


 void push(char n)
 {
 if(isFull() == false)
 {
     top++;
     arr[top] = n;
 }
}

char pop()
{
 if(isEmpty() == false)
 {
     char x = arr[top];
     top--;
     return x;
 }
 else
    return -1;
}

char Top()
{
 if(isEmpty() == false)
 {
    return arr[top];
 }
 else
    return -1;
}
Stack{
 delete []arr;
 }

};

int main()
{
int size=0;


string LineCode;
cout<<"Enter a String : ";
  cin >> LineCode;



    size = LineCode.length();

    Stack s1(size);


    char compare;

    for(int i=0;i<=size;i++)
    {

 if(LineCode[i]=='(' || LineCode[i] == '{' || LineCode[i] =='[')

 s1.push(LineCode[i]);

 else if(LineCode[i]==']')
 {
     if(s1.isEmpty()==false){
                    compare =  s1.pop();
                if(compare == 91){}
                    else
                        {
                        cout<<" Error Founded";
                            return 0;}
        }
            else
            {
               cout<<" Error Founded";
               return 0;
            }

 } else if(LineCode[i] == ')')
 {
     if(s1.isEmpty() == false)
     {
         compare = s1.pop();
         if(compare == 40){}
         else{
            cout<<" Error Founded";
                            return 0;
         }
     }else
     {
        cout<<"Error Founded";
               return 0;
     }
 }else if(LineCode[i] == '}')
 {
       if(s1.isEmpty() == false)
     {
         compare = s1.pop();
         if(compare == 123){}
         else{
            cout<<" Error Founded";
                            return 0;
         }
     }else
     {
        cout<<" Error Founded";
               return 0;
     }


 }
}

if(s1.isEmpty()==true)
{
    cout<<"No Error in Program:\n";
}
else
{
     cout<<" Error Founded";
}

 return 0;
}