How to dynamically add brackets to a boolean expression?

Question

I'm writing a program in Java that is supposed to function as a truth table generator for a boolean expression. However, I'm having a lot of trouble with the brackets. The errors start when a pair of brackets enclose the entire expression (produces a runtime error), or if there aren't enough brackets in the expression (producing the wrong result).

Here's all my code:

        import javax.swing.*;
        import java.awt.*;
        import java.awt.event.*;
        import java.util.*;
        import java.lang.Math;

        public class BooleanAlgebra
        {
           public static void main(String[] args)
           {
              new BooleanAlgebra();
           }

           private JFrame frame;
           private JPanel panel;
           private JTextField textField;
           private JButton and;
           private JButton or;
           private JButton not;
           private JButton nor;
           private JButton nand;
           private JButton xor;
           private JButton xnor;
           private JPanel panel2;
           private JButton generate;
           private JButton close;
           private ArrayList<Character> variables;
           private char[] chars;

           public BooleanAlgebra()
           {
              frame = new JFrame("Boolean Algebra");
              frame.setSize(new Dimension(800, 800));
              textField = new JTextField("(x+y)");

              and = new JButton("AND   [ x & y ]");
              or = new JButton("OR   [ x + y ]");
              not = new JButton("NOT   [ ! x ]");
              nor = new JButton("NOR   [ ! ( x + y ) ]");
              nand = new JButton("NAND   [ ! ( x & y ) ]");
              xor = new JButton("XOR   [ ( x & ! y ) + ( ! x & y ) ]");
              xnor = new JButton("XNOR   [ ( x & y ) + ( ! x & ! y ) ]");
              generate = new JButton("Generate Table");
              close = new JButton("Exit");

              ButtonHandler buttons = new ButtonHandler();
              and.addActionListener(buttons);
              or.addActionListener(buttons);
              not.addActionListener(buttons);
              nor.addActionListener(buttons);
              nand.addActionListener(buttons);
              xor.addActionListener(buttons);
              xnor.addActionListener(buttons);
              generate.addActionListener(buttons);
              close.addActionListener(buttons);

              panel2 = new JPanel();
              panel2.setLayout(new GridLayout(1, 2));
              panel2.add(generate);
              panel2.add(close);

              panel = new JPanel();
              panel.setLayout(new GridLayout(9, 1));
              panel.add(textField);
              panel.add(and);
              panel.add(or);
              panel.add(not);
              panel.add(nor);
              panel.add(nand);
              panel.add(xor);
              panel.add(xnor);
              panel.add(panel2);

              frame.add(panel);
              frame.setLocationRelativeTo(null);
              frame.setVisible(true);
              frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
           }

           private boolean isLetter(char a)
           {
              if((a > 64 && a < 91) || (a > 96 && a < 123))
              {
                 return true;
              }
              return false;
           }

           private void generate()
           {
              chars = ("(" + textField.getText() + ")").toCharArray();
              variables = new ArrayList<Character>();

              for(int i = 0; i < chars.length; i++)
              {
                 if(isLetter(chars[i]))
                 {
                    if(!variables.contains(chars[i]))
                    {
                       variables.add(chars[i]);
                    }
                 }
              }

              Collections.sort(variables);
              String[] heads = new String[variables.size() + 1];
              for(int i = 0; i < heads.length - 1; i++)
              {
                 heads[i] = variables.get(i).toString();
              }
              heads[heads.length - 1] = textField.getText();

              int row = (int)Math.pow(2, variables.size());
              int column = variables.size() + 1;
              int count = 0;
              int max = 1;
              Integer[][] array = new Integer[row][column];

              for(int a = column - 2; a >= 0; a--)
              {
                 for(int b = 0; b < row; b++)
                 {
                    if(count < max)
                    {
                       array[b][a] = 0;
                       count++;
                    }
                    else if(count >= max)
                    {
                       array[b][a] = 1;
                       count++;
                       if(count == max * 2)
                       {
                          count = 0;
                       }
                    }
                 }
                 max = max * 2;
              }

              for(int i = 0; i < row; i++)
              {
                 array[i][column - 1] = 0;
              }

              int[][] arrayCopy = new int[row][column];
              for(int i = 0; i < row; i++)
              {
                 for(int j = 0; j < column; j++)
                 {
                    arrayCopy[i][j] = array[i][j];
                 }
              }
              for(int i = 0; i < row; i++)
              {
                 array[i][column - 1] = calculate(arrayCopy[i]);
              }

              JTable table = new JTable(array, heads);
              JFrame frame2 = new JFrame(textField.getText());
              frame2.add(new JScrollPane(table));
              frame2.pack();
              frame2.setVisible(true);
              table.setEnabled(false);
           }

           private int calculate(int[] array)
           {
              Stack<Character> ops  = new Stack<Character>();
              Stack<Integer> values = new Stack<Integer>();

              for(int i = 0; i < chars.length; i++)
              {
                 char s = chars[i];
                 if      (s == '(')               ;
                 else if (s == '+')    ops.push(s);
                 else if (s == '&')    ops.push(s);
                 else if (s == '!')    ops.push(s);
                 else if (s == ')')
                 {
                    char operation = ops.pop();
                    int v = values.pop();
                    if      (operation == '+')    v = or(values.pop(), v);
                    else if (operation == '&')    v = and(values.pop(), v);
                    else if (operation == '!')    v = not(v);
                    values.push(v);
                 }
                 else if(isLetter(s))
                 {
                    values.push(array[variables.indexOf(s)]);
                 }
              }
              return values.pop();
           }

           private int and(int a, int b)
           {
              if(a == 1 && b == 1)
              {
                 return 1;
              }
              return 0;
           }

           private int or(int a, int b)
           {
              if(a == 0 && b == 0)
              {
                 return 0;
              }
              return 1;
           }
           private int not(int a)
           {
              if(a == 1)
              {
                 return 0;
              }
              return 1;
           }

           public class ButtonHandler implements ActionListener
           {
              public void actionPerformed(ActionEvent event)
              {
                 if(event.getSource() == and)
                 {
                    textField.setText(textField.getText() + "(x&y)");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == or)
                 {
                    textField.setText(textField.getText() + "(x+y)");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == not)
                 {
                    textField.setText(textField.getText() + "(!x)");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == nor)
                 {
                    textField.setText(textField.getText() + "!(x+y)");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == nand)
                 {
                    textField.setText(textField.getText() + "!(x&y)");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == xor)
                 {
                    textField.setText(textField.getText() + "(x&(!y))+(((!x)&y))");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == xnor)
                 {
                    textField.setText(textField.getText() + "(x&y)+(((!x)&(!y)))");
                    textField.requestFocus(true);
                 }
                 if(event.getSource() == generate)
                 {
                    generate();
                 }
                 if(event.getSource() == close)
                 {
                    System.exit(0);
                 }
              }
           }
        }

I need help making this work without the user having to input the brackets correctly themselves (I want the program to fix up the expression, or somehow evaluate it without waiting for a close bracket like I did here).

To test the code and see the errors, input the following when running it:

 (x+y) --> runtime error because brackets surround the whole expression
 x+y+z --> incorrect output table
 x+y   --> works
 x&y   --> works
 !!x   --> incorrect output table

Please explain this to me. Thanks!

You need to write some sort of LL(1) parser to parse this correctly. — M. Shaw, Jun 08 '15 at 22:00
Wrong results mean there is a 0 where there should be a 1 and vise versa. Runtime error involves EmptyStackException. — user3314809, Jun 09 '15 at 16:33

score 1 · Accepted Answer · edited May 23 '17 at 11:51

In your generate method you have declared the following thing:

chars = ("(" + textField.getText() + ")").toCharArray();

However, from your GUI there is actually an entry coming with braces, like (x+y) which basically change the value of chars to ((x+y)).

In calculate you pop however on closing ) characters which on the second brace returns an EmptyStackException. If you remove the braces either from the text-fields in general or from the line quoted above your table should print out fine.

Regarding the input-failure at (!!x): You pop only a single operation from the stack ignoring if there are multiple operations available.

As you asked for how to solve your issue that only one operator is used:

You can try to break down an equation like a && b || (c && d) && !e into its own segments and evaluate each term and combine all those terms at the end to a result similar to an earlier post I did which presents a simple rule engine in plain Java. Note however, that I did not guarantee binding-strength correctness nor did I include braces in this sample - therefore its just a very basic demo of a rule engine!

Following OO principley, you could create an Expression class which And, Or, Not, Term, ... are children of and include a boolean evaluate() method which propagates the call down to the respective term and its binding. The equation from above therefore could be expressed with a more code like approach similar to this f.e:

Expression terms = new Or(
    new And(new Term("a", ...), new Term("b", ...)), 
    new And(new Term("c", ...), 
        new And(new Term("d", ...), new Not(new Term("e", ...))
    )
);
boolean value = terms.evaluate();

To obtain a structure like the one from above, you basically start with an empty stack and iterate through all tokens from the equation. The stack will hold currently open expressions. Therefore, you start by retrieving the first character and decide if it is an operand (( or !) or a letter. If an expression was found you can create a new class representation for it and add it to the stack otherwise create a term object based on the letter and assign the corresponding array[variables.indexOf(s)] value which is either 0 or 1 (false or true) to the term.

Then check if there is an element on the stack (peek will return the topmost element from the stack without removing it) and if so add the term to the operand otherwise store it temporarily so you can add it till you hit the operand and add it thereafter. If an operand has all of its fields filled you need to pop it from the stack and assign it (if not already done) to the new topmost element on the stack. This way you achieve nested structure.

However, you have to also consider the binding-order of operations. A brace binds stronger than an and-operation which further binds stronger than an or-operation. Therefore, on hitting a new operation you also need to check the topmost element on the stack if the binding order is stronger than the binding order of the current element. F.e. while iterating through the sample from above the stack currently holds the And operation for a and b and we are currently processing the Or operation. As this binds weaker than And we need to pop this element from the stack and assign it to the left element of the Or operation and push it onto the stack.

This is similar for braces. However, they can have multiple expressions contained and need to be popped from the stack only if a closing brace was parsed.

I hope this gives you enough insights to continue your journey.

Yes I realize that but I still can't get an input of x+y+z to display the correct result. I also do not know how to handle multiple operations, I would require an example if possible. — user3314809, Jun 09 '15 at 16:27
Also, I cannot predict whether the user will enter something like x+y or (x+y) so that's why I have the brackets in order to help the user. But my problem is that I want to be able to handle both an entry of (x+y) and an entry of x+y and produce the same result for both. This is why I need to be able to dynamically add brackets to x+y to change it to (x+y) in the code itself. — user3314809, Jun 09 '15 at 16:29
@user3314809 updated the code with more detailed information on how to handle multiple operations and terms while still being able to evaluate them — Roman Vottner, Jun 09 '15 at 20:59

How to dynamically add brackets to a boolean expression?

1 Answers1