모든 논리 표현식 변수를 배열에 넣기

Question

표현식의 진리표를 인쇄 할 프로그램을 작성 중입니다. 현재 나의 코드는 논리적 인 표현식을 취해이를 입력으로 표시된 것처럼 두 개의 배열로 바꾼다. 논리식 = ((-A) + B)) + C

입력 : : 내 알고리즘

예를 다음과 같은 출력을 충족 도움이 필요

logExp : (, (, -, A,) +, B)), +, C]

indepVar : [A, B, C]

예상 출력 :

배열 : [A, B, C (-A), (-A) + B, ((-A) + B)) + C] // 대괄호를 포함하거나 포함하지 않는 ok.

전류 출력 나는이 알고리즘으로 얻을 :

배열 : [A, B, C, (-A) + B)]

코드 :

public static ArrayList<String> Head(ArrayList<Character> logExp, ArrayList<Character> indepVar){ 
    ArrayList<String> array = new ArrayList<String>(); 
    int count = 0; 
    String str = ""; 

    for(int i = 0; i < indepVar.size(); i++){ 
     array.add(indepVar.get(i).toString()); 
    } 

    for(int i = 0; i < logExp.size(); i++){ 
     if(logExp.get(i)== '(') 
      count++; 
     else if(logExp.get(i) == ')') 
      count--; 
     if(count > 0) 
      str += logExp.get(i); 
     if(count == 0 && str != ""){ 
      array.add(str); 
      str = ""; 
     } 

    } 
    return array; 

나는 매우 아니다 재귀 함수에 대한 경험은 있지만 위의 알고리즘과 비슷한 알고리즘을 시도해 보았습니다. 위의 알고리즘은 문자열을 가져 와서 대괄호 사이의 모든 것을 배열에 추가하여 재귀 적으로 작동해야합니다.

그런 다음 대괄호 사이의 모든 표현식이 배열에 추가 될 때까지 동일한 알고리즘에 인수로 다시 전달합니다. 그러나 그것은 잘 작동하지 못했고 나는 잘못되었다는 것을 알지 못합니다. 어떤 아이디어?

public static ArrayList<String> rec(String str){ 
    int count = 0; 
    char ch; 
    String s = ""; 
    ArrayList<String> array = new ArrayList<String>(); 

    for(int i = 0; i < str.length(); i++){ 
     ch = str.charAt(i); 

     if(ch == '(') 
      count++; 
     if(count > 0) 
      s += ch; 

     if(ch == ')') 
      count--; 

     if(count == 0 && s != ""){ 
      s = s.substring(1, s.length()-1); 
      array.add(s); 
      count = 0; 
      return rec(s); 
     } 
    } 
    return array; 
} 

Answer 1

무엇 현재의 알고리즘을 수행하는 괄호 세트 내부에 아무것도를 추가 할 수 있습니다 : 여기

는 코드입니다. 이 문제의 본질에 비추어 볼 때 재귀 적이어야한다고 생각합니다. (의사 코드)

간단한 해결책은 다음과 같습니다

main_method (indep, expr): 
    add all of indep to array 
    recur (expr,array) 

recur (expr,array): 
    find expression in parens 
    recur (thing_in_parens,array) 
    add expr to array 

난이 도움이되기를 바랍니다!

Answer 2

나는 이것이 당신의 예상 출력을 얻을 정확히 작동한다면 모르겠지만 개봉 된 나는 공식을했다면 같은 주요 연산자에 따라 논리적 공식을 깨려고하는 경우 :

(AVB) - > C

주 연산자는 "->"입니다. 그리고 수식에 당신이 준 :

((-A) + B)) + C

는 "+"가 될 것입니다.그런 다음 수식 문자열을 반복하고 수 변수에서 왼쪽 및 오른쪽 괄호를 추적 할 수 있습니다. 수식의 한 지점에 도달하면 바로 왼쪽 및 오른쪽 수와 같음을 나타내는 문자가 주 연산자가됩니다. 뭔가 같은 :

이

ArrayList<String> subFormulas = new ArrayList<>(); 
String[][] parseFormulas(String formula) { 
    base case where if formula doesnt have parentheses return the operands 

    subFormulas.add(formula); 
    for (int i = 0; i < formula.length(); i++) { 
     if (formula.charAt(i) == '(') 
      countl++; 
     if (formula.charAt(i) == ')') 
      countr++; 
     if ((countl == countr) && countl != 0) { 
      indexOfOp = i; 
      break; 
     } 
    } 

    // for a formula "A op B" 
    parseFormulas(formula.substring(0, indexOfOp + 1));//A 
    parseFormulas(formula.substring(indexOfOp + 2, formula.length()));//B 

} 

이 방법은 작동 할 수 있지만, 개봉 진실을 인쇄하려고하면 그냥 쉽게 될 수있다 : 지금 당신은 재귀이 일반적인 아이디어를 사용할 수있는이 작업을 수행하려면

for (int i = 0; i < formula.length(); i++) { 
     if (formula.charAt(i) == '(') 
      countl++; 
     if (formula.charAt(i) == ')') 
      countr++; 
     if ((countl == countr) && countl != 0) { 
      indexOfOp = i; 
      break; 
     } 
    } 

표를 사용하여 postfix 표기법을 사용하여 수식의 진리 값을 구문 분석하고 계산합니다. 당신은 당신의 변수에 대한 진리 값의 모든 콤보를 가져 와서 진리표를 만드는 것과 결합시킵니다. 다음은이 아이디어를 실행에 불쌍한 내 시도입니다 :

이

public class TruthTable { 

//highest order of precedence going from the right of array 
char[] operators = {'<', '>', 'v', '&', '~'}; 

//list of variables 
char[] alphabet = { 
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 
     'h', 'i', 'j', 'k', 'l', 'm', 'n', 
     'o', 'p', 'q', 'r', 's', 't', 'u', 
     'w', 'x', 'y', 'z', 'A', 'B', 
     'C', 'D', 'E', 'F', 'G', 'H', 'I', 
     'J', 'K', 'L', 'M', 'N', 'O', 'P', 
     'Q', 'R', 'S', 'T', 'U', 'W', 
     'X', 'Y', 'Z' 
}; 


public static void printString(String[][] s) { 
    for (int i = 0; i < s.length; i++) { 
     System.out.print("{"); 
     for (int j = 0; j < s[0].length; j++) { 
      System.out.print(s[i][j]); 
      if (!(j == s[0].length - 1)) { 
       System.out.print(" "); 
      } 
     } 
     System.out.println("}"); 
    } 

} 
public static int indexOf(ArrayList<Character> list, Character c) { 
    int index = 0; 
    for (int i = 0; i < list.size(); i++) { 
     if (list.get(i) == c) { 
      index = i; 
     } 
    } 
    return index; 
} 
public static boolean contains(ArrayList<Character> list, Character c) { 
    for (Character i : list) { 
     if (i == c) return true; 
    } 
    return false; 
} 
public static boolean contains(char[] chars, Character c) { 
    for (int i = 0; i < chars.length; i++) { 
     if (chars[i] == c) return true; 
    } 
    return false; 
} 


/** 
* used this w/ makeTable to print to console 
*/ 
public static String[][] makeEven(String[][] table){ 
    for(int j=0;j<table[0].length;j++){ 
     int largestString=0; 
     for(int i=0;i<table.length;i++){ 
      if(table[i][j].length()>largestString) 
       largestString = table[i][j].length(); 
     } 
     for(int i=0;i<table.length;i++){ 
      if(table[i][j].length()<largestString){ 
       int diff=((largestString-table[i][j].length())/2); 
       int middle=((diff/2)+1); 
       String tmp = table[i][j]; 
       table[i][j]=""; 
       int count=0; 
       while(table[i][j].length()!=largestString){ 
        count++; 
        if(count!=middle) 
         table[i][j] += " "; 

        else 
         table[i][j] +=tmp; 

       } 
      } 
     } 
    } 
    return table; 
} 

/** 
* POSSIBLY WORST METHOD EVER DEVISED FOR PRINTING A TABLE 
* @return the table to be printed 
*/ 
public static String[][] makeTable(String formula, char[] variables, ArrayList<ArrayList<Boolean>> combos) { 
    int spacing = 2; 
    String[][] result = new String[combos.size() + 3][(spacing + 1) * variables.length + formula.length() + 2 * spacing]; 
    for (int i = 0; i < result.length; i++) { 
     int count = 0; 
     int k = 0; 
     for (int j = 0; j < result[0].length; j++) { 
      if (i == 1) { 
       if(j < (variables.length * (spacing + 1) + spacing)) { 
        if ((j % (spacing + 1) == 2)) { 
         result[i][j] = "" + variables[k]; 
         k++; 
        } else result[i][j] = "*"; 
       } 
       else{ 
        if (j == (variables.length * (spacing + 1) + spacing + (formula.length()/2))) { 
         result[i][j]=formula; 
        } else result[i][j] = " "; 
       } 
      } 
      if (i == 0 || i == (result[0].length - 1) || i == 2) 
       result[i][j] = "*"; 

      if (j < (variables.length * (spacing + 1) + spacing) && (i > 2)) { 
       if (j % (spacing + 1) == 2) { 
        if (combos.get(i - 3).get(count)) 
         result[i][j] = "True"; 
        else result[i][j] = "False"; 
        count++; 
       } else result[i][j] = "*"; 
      } 
      else if(i>2) { 
       if (j == (variables.length * (spacing + 1) + spacing + (formula.length()/2))) { 
        if (combos.get(i - 3).get(count)) result[i][j] = "True"; 
        else result[i][j] = "False"; 
        count++; 
       } else result[i][j] = " "; 
      } 

     } 
    } 
    return result; 
} 


/** 
* @param n number of variables in logic formula 
* @return 2d list where each 1d list has T/F vals 
*   for that row in table 
*/ 
public static ArrayList<ArrayList<Boolean>> combos(int n) { 
    ArrayList<ArrayList<Boolean>> output = new ArrayList<>(); 
    for (int i = 1; i <= Math.pow(2, n); i++) { 
     ArrayList<Boolean> tmp = new ArrayList<>(); 
     String combo = Integer.toBinaryString(i - 1); 
     while (combo.length() < n) { 
      combo = "0" + combo; 
     } 
     for (int j = 0; j < combo.length(); j++) { 
      if (combo.charAt(j) == '0') 
       tmp.add(false); 
      else tmp.add(true); 
     } 
     output.add(tmp); 
    } 
    return output; 
} 

/** 
* @param formula logic formula like "(a&b)>c" 
* @return character array of variables in formula 
*/ 
public char[] getVariables(String formula) { 
    String vars = ""; 
    for (int i = 0; i < formula.length(); i++) { 
     if (contains(alphabet, formula.charAt(i))) 
      vars += formula.charAt(i); 
    } 
    char[] variables = new char[vars.length()]; 
    for (int i = 0; i < vars.length(); i++) { 
     variables[i] = vars.charAt(i); 
    } 
    return variables; 
} 

/** 
* @param formula string to test 
* @return true if parentheses are validly placed 
*/ 
public boolean parenMatch(String formula) { 
    Stack parenStack = new Stack(); 
    for (int i = 0; i < formula.length(); i++) { 
     char token = formula.charAt(i); 
     if (token == '(') { 
      parenStack.push(token); 
     } else if (token == ')') { 
      if (parenStack.isEmpty()) { 
       return false; 
      } 
      parenStack.pop(); 
     } 
    } 
    if (parenStack.isEmpty()) { 
     return true; 
    } 
    return false; 
} 

/** 
* Shunting-yard 
* 
* @param formula logic formula 
* @return postfix expression 
*/ 
public String parseFormula(String formula) { 
    if (!parenMatch(formula)) { 
     System.out.println("this formula: '" + formula + "' doesnt work, parentheses dont match"); 
     String result = ""; 
     return result; 
    } 
    ArrayList<Character> infix = new ArrayList<Character>(); 
    for (int i = 0; i < formula.length(); i++) { 
     infix.add(formula.charAt(i)); 
    } 
    ArrayList<Character> removeFromInfix = new ArrayList<Character>();//remove spaces from input 
    for (Character c : infix) { 
     if (c == ' ') removeFromInfix.add(c); 
    } 
    for (Character c : removeFromInfix) { 
     infix.remove(c); 
    } 


    ArrayList<Character> operators = new ArrayList<Character>(); 
    ArrayList<Character> alphabet = new ArrayList<Character>(); 
    for (int i = 0; i < this.operators.length; i++) { 
     operators.add(this.operators[i]); 
    } 
    for (int i = 0; i < this.alphabet.length; i++) { 
     alphabet.add(this.alphabet[i]); 
    } 


    Stack<Character> operatorStack = new Stack<Character>(); 
    Queue<Character> inputTokens = new Queue<Character>(); 
    Queue<Character> output = new Queue<Character>(); 


    for (int i = 0; i < infix.size(); i++) { 
     inputTokens.enqueue(infix.get(i)); 
    } 

    while ((!inputTokens.isEmpty())) { 
     Character token = inputTokens.dequeue(); 

     //if its a character in alphabet 
     if (contains(alphabet, token)) output.enqueue(token); 

      //if its an operator 
     else if (contains(operators, token)) { 
      if (operatorStack.empty()) { 
       operatorStack.push(token); 
      } else { 
       Character topOperator = operatorStack.peek(); 
       //while (precedence of op on top of operator stack > token) enqueue op onto result 
       while ((indexOf(operators, operatorStack.peek())) > (indexOf(operators, token))) { 
        output.enqueue(topOperator); 
        topOperator = operatorStack.peek(); 
        operatorStack.pop(); 

        if (operatorStack.isEmpty()) { 
         break; 
        } 
       } 
       operatorStack.push(token); 
      } 
     } else if (token == '(') { 
      operatorStack.push(token); 
     } else if (token == ')') { 
      while (!(operatorStack.peek().equals('('))) { 
       output.enqueue(operatorStack.peek()); 
       operatorStack.pop(); 
      } 
      operatorStack.pop(); 
     } 
    }//end while 

    while (!operatorStack.isEmpty()) { 
     output.enqueue(operatorStack.pop()); 
    } 

    String result = ""; 
    for (char c : output) { 
     result += c; 
    } 
    return result; 
} 

/** 
* @param postfix given from parseFormula 
* @param inputs true and false values in the order the variables are listed in postfix 
* @return resulting true or false value of posfix expression 
*/ 
public boolean evalPostfix(String postfix, ArrayList<Boolean> inputs) { 
    //to make sure not to change the inputs outside of this function 
    ArrayList<Boolean> inputsCopy = new ArrayList<>(); 
    for (int i = 0; i < inputs.size(); i++) { 
     inputsCopy.add(inputs.get(i)); 
    } 

    Stack<Boolean> output = new Stack<>(); 
    for (int i = 0; i < postfix.length(); i++) { 
     char token = postfix.charAt(i); 
     if (!contains(operators, token))//if variable 
      output.push(inputsCopy.remove(0)); 

     else {//if operator 
      boolean result = false; 
      if (token == '~') 
       result = !output.pop(); 
      else { 
       boolean A = output.pop(); 
       boolean B = output.pop(); 
       if (token == '&') 
        result = A && B; 
       else if (token == 'v') 
        result = A || B; 
       else if (token == '>') 
        result = !B || A; 
      } 
      output.push(result); 
     } 
    } 
    return output.pop(); 
} 


public static void main(String[] args) throws Exception { 
    TruthTable t = new TruthTable(); 

    String formula = "((pvq)&(jvk))>r"; 
    char[] variables = t.getVariables(formula); 

    String postfix = t.parseFormula(formula); 
    ArrayList<ArrayList<Boolean>> combos = combos(variables.length); 
    for (ArrayList<Boolean> combo : combos) { 
     combo.add(t.evalPostfix(postfix, combo)); 
    } 
    printString(makeEven(t.makeTable(formula,variables,combos))); 

} 

}

은 필자가 간신히 그것을 테스트는하지만이 아이디어는 여전히 괜찮은 될 수있다 생각합니다.