在 java 中测试公式中的括号是否匹配，我的算法是否正确？

Question

我对这个问题的分析如下：括号匹配的条件有四种：{{()}}、{}[]<>、<{}[]>、{<>[]}<> 所以如果我只考虑这 4 个匹配形式，它可能会很复杂。所以我试图找出括号何时不匹配。如果我让 { 和 } 成为一对，我会发现如果一个括号在奇数位置，那么他的对必须在偶数位置，反之亦然。以{<>[]}<>为例，{在第1位为奇数位，}在第6位为偶数位。因此我用数字来标记它们 '()'--1,9; '[]'--2,8; '<>' --3,7; '{}' --4,6 所以如果两个数字加起来等于 10 那么这两个数字代表一对。然后我用这些数字来表示括号结构。然后我在奇数位置拉出括号，在偶数位置拉出括号（用数字表示），然后将奇数位置和偶数位置的每个项目相互相加，看看是否有加起来为 10 的匹配项，如果没有，我说这是一场比赛。我的代码如下：

/** Matching Brackets
  * Tony
  */
import java.util.*;

public class Solution19 {

  public static String process(String n) {
    /** build a condition combination: */
    String newString = "";
    for (int i = 0; i < n.length(); i++) {
      if (n.charAt(i) == '(' || n.charAt(i) == ')' || n.charAt(i) == '[' || n.charAt(i) == ']' 
            || n.charAt(i) == '<' || n.charAt(i) == '>' || n.charAt(i) == '{' || n.charAt(i) == '}') {
        newString += n.charAt(i);
      }
    }
    return newString;
  }


  public static String numForm(String s) {
    String newone = "";
    for (int i = 0; i < s.length(); i++) {
      switch(s.charAt(i)) {
        case '(': newone += "1 ";break;
        case ')': newone += "9 ";break;
        case '[': newone += "2 ";break;
        case ']': newone += "8 ";break;
        case '<': newone += "3 ";break;
        case '>': newone += "7 ";break;
        case '{': newone += "4 ";break;
        case '}': newone += "6 ";break;
      }
    }
    return newone;
  }

  public static int[] intArray(String m) {
    String[] stringArray = m.split(" ");
    int[] intArr = new int[stringArray.length];
    for (int i = 0; i < stringArray.length; i++) {
      intArr[i] = Integer.parseInt(stringArray[i]);
    }
    return intArr;
  }

  public static void printArray (int[] array) {
    for (int n : array) {
      System.out.print(n + " ");
    }
  }

  public static int[] oddPosition (int[] array) {
    int [] oddNumbers = new int[array.length / 2];
    int j = 0;
    for (int i = 0; i < array.length; i++) {
      if ((i + 1) % 2 != 0) {
        oddNumbers[j] = array[i];
        j ++;
      }
    }
    return oddNumbers;
  }

  public static int[] evenPosition (int[] array) {
    int [] evenNumbers = new int[array.length / 2];
    int j = 0;
    for (int i = 0; i < array.length; i++) {
      if ((i + 1) % 2 == 0) {
        evenNumbers[j] = array[i];
        j ++;
      }
    }
    return evenNumbers;
  }

  public static boolean addsUpten (int [] array) {
    boolean conditionSum = false;
    boolean conditionSingle = false;
    for (int i = 0; i < array.length; i++) {
      int d = 0;
      while (i + d < array.length) {
        if (array[i] + array[i+d] == 10) {
          conditionSingle = true;
        }
        conditionSum = (conditionSum || conditionSingle);
        d ++;
      }
    }
    return conditionSum;
  }




  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int times = sc.nextInt();
    String voider = sc.nextLine();

    for (int i = 0; i < times; i ++) {
      String formula = sc.nextLine();
      String processed = process(formula);

      String numFormed = numForm(processed);
      // System.out.println(numFormed);
      int[] numArray = intArray(numFormed);

      if (numArray.length % 2 != 0) {
        System.out.print("0 ");
      }
      else {
        int[] oddNumbers = oddPosition(numArray);

        int[] evenNumbers = evenPosition(numArray);


        if (addsUpten(oddNumbers) || addsUpten(evenNumbers) == true) {
          System.out.print("0 ");
        }
        else {
          System.out.print("1 ");
        }
      }
    }
  }
}

如我所料，它应该可以工作，并且在我输入时确实可以工作：

4
(a+[b*c]-{d/3})
(a + [b * c) - 17]
(((a * x) + [b] * y) + c
auf(zlo)men [gy<psy>] four{s}

它给我输出：1 0 0 1（1 表示匹配，0 表示不匹配）。但是，当我输入像 [^]<t>(z){<[^]<w>[{f}c]y[-][v]{<y>g<+( )>(c){w{a{t}}}}>((a)w)} 这样更长的内容时，它是一个匹配项，但它给了我 0。我想知道我确定它是否匹配的方式是对还是错？我错过了什么？抱歉，代码很长，只是想知道 ("I find out if one bracket is on the odd position then his pair must be in a even position, vice versa.") 这种描述括号匹配的方式是对还是错？谢谢！

Answer 1

您的方法有一个根本问题 - 它不能很好地支持嵌套。

你可以通过创建一堆括号来解决这个问题：

当您看到左括号时，将其压入堆栈
当您看到一个右括号时，您会从堆栈中弹出一个应该与之配对的左括号
如果堆栈中的对匹配，则继续
如果对不匹配，或者堆栈为空，报告不匹配
如果循环结束时栈不为空，同样报错。

在 java 中测试公式中的括号是否匹配，我的算法是否正确？

in java to test if the brackets in a formula is matching, is my algorithm right?

java

algorithm

math

brackets