Logical expressions may combine many connectives applied according to the follow

Question

Logical expressions may combine many connectives applied according to the following operation hierarchy: all ~ are applied first next all & are applied next all v are applied next all --> are applied finally all <--> are applied Parentheses may be used to override this hierarchy. A Logical expression which always evaluates to true is called a tautology. Example: (P --> Q) <--> (~P v Q) is a tautology, because it is true for all possible combinations of true/false values of P and Q. Write a program that tells you if the expression entered is a tautology or not. Assume that you have no more than three propositional symbols in your expressions -- call them P, Q, R. You must use the linked list implementation of the data structures needed. Using java, thanks

Explanation / Answer

import java.util.*;
import java.util.Scanner;

public class Tautology
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
LinkListADT s=new LinkListADT();
  
System.out.print("Enter the expression: ");
String expression = sc.next();
  
expression = s.postfix(expression);
System.out.println("------------------------------------------");
s.Evaluation(expression);
System.out.println("------------------------------------------");
}
}

interface LLStack {

public void push (Object item);
public Object pop();
public Object size();
public boolean empty();
public Object peek();

}

class Node {

public Object data;
public Node next;

public Node () {
this(0, null); }

public Node (Object d) {
data = d; }

public Node (Object d, Node n) {
data = d;
next = n; }

public void setData (Object newData) {
data = newData; }

public void setNext (Node newNext) {
next = newNext; }

public Object getData () {
return data; }

public Node getNext () {
return next; }

public void displayNode () {
System.out.print (data); }
}

class LinkListADT implements LLStack {

private Node top;
private int size;

public LinkListADT () {
top = null;
size = 0;}

public boolean empty () {
return (top == null); }
  
public Object size () {
int count = 0;
Node current = top;
while (current != null) {
count++;
current = current.getNext();
}
return count;
}   

public void push(Object e){
Node tmp = new Node(e);
tmp.next = top;
top = tmp;
}
public Object pop(){

Object e = top.data;
top = top.next;
return e;
}
public Object peek(){

Object e = top.data;
  
return e;
}
  
public String postfix(String node)
{
String output="";
LinkListADT S=new LinkListADT();
for(int i=0;i<node.length();i++)
{
char c=node.charAt(i);
  
if(c==('>')||c==('<')||c==('v')||c==('&')||c==('~')||c==('#'))
{while(!S.empty() && stackpriority(S.peek())>= stackpriority(c))
output+=S.pop();
S.push(c);
}
else if(c=='(')
{
S.push(c);
}
else if(c==')')
{
while(!S.peek().equals('('))
output+=S.pop();
S.pop();
}
else
output+=c;
}
while(!S.empty()){
output+=S.pop();}

return output;
}

public void Evaluation(String x)
{
String s= "";
String p="";

LinkListADT S=new LinkListADT();
for(int i=0;i<x.length();i++)
{
char c=x.charAt(i);
char z = 'T';
char y = 'F';
  
if (c=='P'||c=='Q'||c=='R')
{
S.push(z);
s+=z;
}

else if(c=='>')
{
if(S.peek() == 'T' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'T' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'F' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(y);}
else if (S.peek() == 'F' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(z);}
  
s+=c;
}
else if(c=='<')
{
if(S.peek() == 'T' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'T' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(y);}
else if(S.peek() == 'F' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(y);}
else if (S.peek() == 'F' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(z);}

s+=c;
}
else if(c=='&')
{   
if(S.peek() == 'T' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'T' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(y);}
else if(S.peek() == 'F' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(y);}
else if (S.peek() == 'F' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(y);}

s+=c;
}
else if(c=='v')
{
if(S.peek() == 'T' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'T' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(z);}
else if(S.peek() == 'F' && S.peek() == 'T'){
S.pop();
S.pop();
S.push(z);}
else if (S.peek() == 'F' && S.peek() == 'F'){
S.pop();
S.pop();
S.push(y);}
  
s+=c;
}
else if(c=='~')
{
if(S.peek() == 'T'){
S.pop();
S.push(y);}
else{
S.pop();
S.push(z);}
  
s+=c;
}
}
System.out.println("THE POSTFIX = "+ x);
System.out.println("THE RESULT = "+ S.pop());
}
  
  
public int stackpriority(Object node)

{
if(node== '>')
return 1;
if(node=='<')
return 2;
if(node=='&')
return 4;
if(node=='v')
return 3;
if(node=='~')
return 5;
if(node=='(')
return 0;
  
return 7;
}

}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.