0

在过去的几个小时里，我一直试图解决这个问题，但我就是不明白。我知道必须有一种数学计算来计算它，但我不知道如何准确计算它。我知道这段代码没有意义，因为我完全迷路了，我将不胜感激任何提示或帮助，以帮助我更接近解决方案。

我问了我的教授，他告诉我一个提示，它类似于使用字母表的排列/组合，例如 26^3 用于 3 种不同的组合，但这对我没有多大帮助。

我知道的：

  1. 字符串中给出的输入有 796 个字符，我必须找到 796 个字符可以采用平衡括号形式的所有可能方式。

  2. 由于它必须以 '(' 开头并以 ')' 结尾，因此每种情况必须有 2 个括号。所以它可以是'()()(xc)(cvs)'。因此，这意味着数学计算必须涉及每个 char(s) 2*(something)，因为它必须是平衡的。

  3. 我需要使用 rest(%) 运算符递归地查找每个案例，但是当我接受 a charin 而不是a 时，我该怎么做int？

我不知道的是：

  1. 我将如何分析每个案例？如果没有简单的公式来计算输入，这不会花费很长时间或大量代码吗？

  2. 我需要很多 -if语句或递归吗？

问题：

令 Σ = {), (}。令 L ⊆ Σ* 是正确平衡括号的字符串集合。例如，(())() 在 L 中，而 (()))( 不在 L 中。形式上， L 递归定义如下。

ε ∈ L

串 x ≠ ε 在 L 当且仅当 x 的形式为 (y)z，其中 y 和 z 在 L 中。

n 是 0 到 999 之间的特定 3 位数字。

计算 f(n) mod 997

您可能会发现一些有用的事实：如果 n1，n2 是 N（自然数）的成员，那么，

(n1 x n2) mod 997 和 (n1 + n2) mod 997

n = 796（这对我来说是特定的，在这种情况下这将是给定的输入）

所以我必须“计算 f(796) mod 997 = ?” 使用程序。在这种情况下，我将简单地使用 java 来回答这个问题。

代码：

import java.util.*;
public class findBrackets
{

    public static void main(String[] args)
    {

        String n;
        int answer = 0;
        Scanner input = new Scanner(System.in);

        System.out.println("Input String");
        n = input.nextLine();

           // probably wrong because a string can start as x(d))c(()...

        for(int i = 0; i < n; i++)
        {
           if(n[i] != '(' || n[i] != ')' || n[i] != null || n[i] != " ") { 

             answer = 2 * (Integer.parseInt(n[i]); // how can i calculate if its a char

              // i have to use mod % operator somewhere but I don't know where?
           }

        }

       System.out.println("f(796) mod 997 = " + answer);

    }
 }
4

3 回答 3

2

您可能会发现以下事实很有用：n 对平衡括号的字符串数由第 n 个加泰罗尼亚数给出，其确切值为

(2n)！/（n！（n + 1）！）

您应该能够通过使用有关产品和总和如何在模数上分布的提示直接计算此值 mod 997。

希望这可以帮助！

于 2014-09-17T19:22:26.317 回答
0

您需要执行此操作：

public static void main (String[]args) {
    String str = "((1+2)*(3+4))-5";
    if(isValid(str)){
        expandString(str);
    }
}

public static boolean isValid(String s) {
    int totalParenthesis = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            totalParenthesis++;
        } else if (s.charAt(i) == ')') {
            totalParenthesis--;
        }
        if (totalParenthesis < 0) {
            return false;
        }
    }
    if (totalParenthesis != 0) {
        return false;
    }
    return true;
}

private static void expandString(String str) {
    System.out.println("Called with : "+str);
    if(!(str.contains("("))){
        evalueMyExpresstion(str);
        return;
    }
    String copyString=str;
    int count=-1,positionOfOpen=0,positionOfClose=0;
    for(Character character : str.toCharArray()) {
        count++;
        if(count==str.toCharArray().length){
            evalueMyExpresstion(str);
            return;
        } else if(character.equals('(')) {
            positionOfOpen=count+1;
        } else if(character.equals(')')) {
            positionOfClose=count;
            copyString = str.substring(0, positionOfOpen - 1) + evalueMyExpresstion(
                        str.substring(positionOfOpen, positionOfClose)) + str.substring(positionOfClose + 1);
            System.out.println("Call again with : "+copyString);
            expandString(copyString);
            return;
        }
    }
}

private static String evalueMyExpresstion(String str) {
    System.out.println("operation : "+str);
    String[] operation;
    int returnVal =0;
    if(str.contains("+")){
        operation = str.split("\\+");
        returnVal=Integer.parseInt(operation[0])+ Integer.parseInt(operation[1]);
        System.out.println("+ val : "+returnVal);
        return Integer.toString(returnVal);
    } else if (str.contains("*")){
        operation = str.split("\\*");
        returnVal=Integer.parseInt(operation[0])* Integer.parseInt(operation[1]);
        System.out.println("* val : "+returnVal);
        return Integer.toString(returnVal);
    } else if (str.contains("-")){
        operation = str.split("\\-");
        returnVal=Integer.parseInt(operation[0])- Integer.parseInt(operation[1]);
        System.out.println("- val : "+returnVal);
        return Integer.toString(returnVal);
    }
    System.out.println(str);
    return Integer.toString(returnVal);
}

输出如下所示：

Called with : ((1+2)*(3+4))-5
operation : 1+2
+ val : 3
Call again with : (3*(3+4))-5
Called with : (3*(3+4))-5
operation : 3+4
+ val : 7
Call again with : (3*7)-5
Called with : (3*7)-5
operation : 3*7
* val : 21
Call again with : 21-5
Called with : 21-5
operation : 21-5
- val : 16
于 2014-09-17T20:30:23.460 回答
0

我仍然不太确定您在问什么，但是可以使用以下方法验证括号是否是有效的放置。我用一个类似的文件浏览了一百页的论文，以确保所有括号在过去都正确关闭。

public static boolean isValid(String s) {
    int openParens = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            // we found an open paren
            openParens++;
        } else if (s.charAt(i) == ')') {
            // we can close a paren
            openParens--;
        }
        if (openParens < 0) {
            // we closed a paren but there was nothing to close!
            return false;
        }
    }
    if (openParens > 0) {
        // we didn't close all parens!
        return false;
    }
    // we did!
    return true;
}
于 2014-09-17T19:25:46.750 回答