Помещение всех переменных логического выражения в массив
Я пишу программу, которая будет печатать таблицу истинности выражения. В настоящее время мой код принимает логическое выражение и превращает его в два массива, как показано на входе. Мне нужна помощь в удовлетворении следующих выводов для моего алгоритма
Пример: логическое выражение = ((-A) + B)) + C
Входные данные:
logExp: [(, (, -, A,), +, B,),), +, C]
indepVar: [A, B, C]
Ожидаемый результат:
массив: [A, B, C, (-A), (-A)+B, ((-A)+B))+C] // нормально с или без скобок.
Токовый выход я получаю с этим алгоритмом:
массив:[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;
}
2 ответа
Я не знаю, будет ли это работать точно, чтобы получить ожидаемый результат, но если вы пытаетесь разбить логическую формулу на основе основного оператора, как если бы у меня была формула:
(AvB) -> C
основным оператором будет "->". И в формуле вы дали:
((-А)+ В))+ С
это будет "+". Тогда вы сможете перебирать строку формулы и отслеживать левую и правую скобки в переменных счетчика, отмечая, что когда вы доберетесь до точки в формуле, где левые и правые значения равны, символ сразу после того, как будет основным оператором что-то вроде:
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;
}
}
Теперь, если вы хотите сделать это рекурсивно, вы можете использовать эту общую идею:
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
}
Этот метод может работать, но может быть проще, если вы пытаетесь распечатать таблицу истинности, использовать постфиксную нотацию для анализа и вычисления значения истинности формулы. Вы комбинируете это с получением всех комбинаций значений истинности для ваших переменных, чтобы составить таблицу истинности. Вот моя неудачная попытка реализовать эту идею:
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)));
}
}
Я только проверил это, но я думаю, что эта идея все еще может быть приличной.
То, что делает ваш текущий алгоритм, это добавить что-нибудь в скобки. Судя по характеру этой проблемы, я думаю, что она должна быть рекурсивной.
Простое решение (в псевдокоде) было бы:
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
Надеюсь, это поможет!