The goal of this assignment set is for you to apply your understanding of argument form validity checks to automate them by implementing code to accomplish this.

Write a Java program to automate checking validity of argument forms. To avoid the complexity of parsing arbitrary argument forms, we have included a parser and evaluator for you to use. Your code should be able to handle a varied selection of negations, conjunctions, disjunctions, and conditionals. Do not hardcode the truth tables, as your code should be able to handle any number of variables. We are giving you an additional file (Evaluator.java or Evaluator.py) to help you evaluate the argument forms. More about how to use this file is included in the template files. It is not necessary to upload this file to Gradescope.

package com.gradescope.validator;

import java.util.*;

final public class Evaluator { final private static char[] operators = {'^', 'V', '~', '>'}; // Evaluates an infix logical expression public static boolean evaluate(String arg, Hashtable vars) throws Exception { LinkedList tokens = lex(arg); LinkedList ast = parse(tokens); boolean value = eval_rpn(ast, vars); return value; }

private static LinkedList lex(String arg) { LinkedList tokens = new LinkedList(); for (char c : arg.toCharArray()) tokens.add(c); return tokens; } public static LinkedList parse(LinkedList tokens) throws Exception{ // Turns an infix arithmetic string into an RPN representation. // Uses the Shunting yard algorithm. This is used to resolve operator // precedence and handle parentheses.

LinkedList output = new LinkedList(); Stack operator_stack = new Stack();

while (tokens.size() > 0) { // Get next token char token = tokens.remove(); if (isOperator(token)) { int precedence = getPrecedence(token); // Pop operators off the stack and push them into the output queue until the next operator // in the stack has a higher precedence (i.e. the operators popped off the stack will be // executed before the current operator) while (operator_stack.size() > 0 && precedence <= getPrecedence(operator_stack.peek())) { output.add(operator_stack.pop()); }

operator_stack.push(token); } else if (token == '(') { operator_stack.push(token); } else if (token == ')') { // Remove operators until the left parenthesis is found while (operator_stack.peek() != '(') { output.add(operator_stack.pop()); }

operator_stack.pop(); // Pop the left paren } else if (isVariable(token)) { output.add(token); } else { throw new Exception(String.format("Token \'%c\' is not a valid token.", token)); } } // Add the rest of the operators into the output in precedence order while (operator_stack.size() > 0) output.add(operator_stack.pop()); return output; } // Evaluates the given parsed text according to reverse polish notation private static boolean eval_rpn(LinkedList rpn, Hashtable vars) throws Exception { Stack stack = new Stack(); char token = ' '; try { while (rpn.size() > 0) { token = rpn.pop(); if (isVariable(token)) { stack.push(vars.get(token)); } else if (token == '^') { boolean operand1 = stack.pop(); boolean operand2 = stack.pop(); stack.push(operand1 && operand2); } else if (token == 'V') { boolean operand1 = stack.pop(); boolean operand2 = stack.pop(); stack.push(operand1 || operand2); } else if (token == '~') { boolean operand = stack.pop(); stack.push(!operand); } else if (token == '>') { boolean operand1 = stack.pop(); boolean operand2 = stack.pop(); stack.push(!operand2 || operand1); } } } catch (EmptyStackException e) { throw new Exception(String.format("Operator \'%c\' did not have enough operands to operate", token)); } // Check to see if the stack length is the correct length if (stack.size() > 1) throw new Exception(String.format("Not enough operators in argument; there were %i operands remaining", stack.size())); if (stack.size() == 0) throw new Exception("Error when evaluating argument. No operands remaining"); // Return the only value on the stack (i.e., the result) return stack.pop(); } private static boolean isVariable(char token) { if ((int) token >= 97 && (int) token <= 122) return true; return false; }

private static boolean isOperator(char token) { for (int i = 0; i < 4; i++) { if (token == operators[i]) { return true; } }

return false; }

// Returns a number denoting when in the order of operations the operator // will be calculated (i.e. * before +). Higher number -> higher precedence private static int getPrecedence(char operator) { switch (operator) { case '>': return 0; case '^': case 'V': return 1; case '~': return 2; case '(': case ')': return -1; default: return -5; } }

}

// DO NOT DELETE THIS LINE!!! package com.gradescope.validator;

// Notes on how to use evaluator(): // Call the evaluator with Evaluator.evaluate(, ). "premise" // is a single string defining the premise or conclusion to test. "variable_dict" is a // Hashtable() object with the variable name as the key and true/false // as the value.

// The only valid operators for premise strings are '^' (and), 'V' (or--CAPITAL v), '~' (not), // and '>' (implies), and you can use parentheses to override the order of operations as usual. // All variables should be lowercase letters and each should only be one character long. Finally, // do not include spaces in the string.

// For example, if you want to test the premise 'p implies q or not r', you should use 'p>qV~r' as // your premise string.

public class Validator { // All of the logic to complete this assignment should be written in this function. // This method accepts two things: An array of strings called premiseList and a // single string called conclusion. These strings should be formatted according to // the structure definded above. Also, this needs to return a boolean variable: true if // the argument form is valid, and false if it is not valid. public boolean validate(String[] premiseList, String conclusion) { return false; } }