Question

This question need to be solved using java coading :-

I. Input

   All input data are from a file "in.dat". The file contains a
sequence of infix form expressions, one per line. The character '$' 
is an end mark. For example, the following file has four infix form 
expressions:

   1 + 2 * 3 ^ ! ( 4 == 5 ) $
   3 * ( 6 - 4 * 5 + 1) + 2 ^ 2 ^ 3 $
   77 > ( 2 - 1 ) + 80 / 4 $
   ! ( 2 + 3 * 4 >= 10 % 6 ) && 20 != 30 || 45 / 5 == 3 * 3 $

Each expression is a sequence of tokens (i.e., constant integers,
operators, and end mark) separated by spaces. There is no variable.


II. Output

   Output data and related information are sent to the screen.
Your program should do the following for each expression:

   (1) printing the expression before it is manipulated;
   (2) showing the converted postfix form expression;
   (3) showing the expression tree;
   (4) printing the fully parenthesized infix form expression;
   (5) reporting the value of the expression.


III. Operators

   The following operators are considered. They are listed in the
decreasing order of precedence.

   Token            Operator            Associativity

    !               logical not         right-to-left
    ^               exponentiation      right-to-left
    *  /  %         multiplicative      left-to-right
    +  -            additive            left-to-right
    <  <=  >  >=    relational          left-to-right
    ==  !=          equality            left-to-right
    &&              logical and         left-to-right
    ||              logical or          left-to-right


IV. Other Requirements

   Since a large amount of information are to be displayed on the
screen, it is mandatory for your program to provide users a prompting
message such as

          Press <Enter> to continue ...

after each expression is processed, so that users have the chance to
check the output of your program carefully.


V. Algorithm: Infix_to_postfix conversion

  Input:  An infix form expression E = t1 t2 t3 ... $,
          which is a sequence of tokens.
  Output: The postfix form expression of E.

  Algorithm: 
  {
    do {
      get the next token t;
      case (t) {
         operand: place t onto the output;
                  break;
        operator: while (stack s is not empty
                    && stacktop(s) is not a left parenthesis)
                    && precedence(stacktop(s)) >= precedence(t)
                       // assuming left-to-right associativity, 
                       // not for the exponentiation operator ^, 
                       // which has right-to-left associativity 
                  {
                        pop(x,s);
                        place x onto the output;
                  }
                  push(t,s);
                  break;
               (: push(t,s);
                  break;
               ): while (stacktop(s) is not a left parenthesis) {
                      pop(x,s);
                      place x onto the output;
                  }
                  pop(x,s);
                  break;
        end mark: while (stack s is not empty) {
                      pop(x,s);
                      place x onto the output;
                  }
                  place the end mark onto the output;
                  break;
      }
    } while (t is not the end mark);
  }

This below is "in.dat file"

12 * 23 <= ( ( ( 3456 ) ) +    ( 6789 ) ) $ 1
4 ^ 3 - ( 2 + 4 * 15 ) - ( 90 / 3 != 30 ) $ 2
! ( 222 < 111 ) + 2 * 3 ^ ( 29 - 3 * 9 ) > 18 && 1234 == 1234 $ 1
( 2 * ( 62 % 5 ) ) ^ ( ( 4 - 2 ) ) - 2 ^ 2 ^ 2 $ 0
( ( 9 / ( 5 - 2 ) + 2 ) * ( 2 ^ 2 * 2 ) - 79 ) || ! ( 65432 > 54321 ) $ 1
( ( 9999 >= 8888 ) + 2 ) * ( 4 / ( 999 - 997 ) ) - 2 ^ ( 5 - 3 ) $ 2

Answer 1

class Node {

char value;
Node left, right;

Node(char item) {
value = item;
left = right = null;
}
}

public class Main
{
   public static void main(String[] args) {
       System.out.println("Hello World");
       try {
//the file to be opened for reading
FileInputStream fis=new FileInputStream("Demo.txt");   
Scanner sc=new Scanner(fis); //file to be scanned
//returns true if there is another line to read
while(sc.hasNextLine()){
System.out.println(sc.nextLine());
promptEnterKey();
postfix_convert(sc.nextLine());
promptEnterKey();
expression_tree(sc.nextLine());
promptEnterKey();
evaluate_exp(sc.nextLine());
}
sc.close(); //closes the scanner
}
catch(IOException e){
e.printStackTrace();
}

   }
   public void promptEnterKey(){
System.out.println("Press \"ENTER\" to continue...");
Scanner scanner = new Scanner(System.in);
scanner.nextLine();
}
   public void postfix_convert(String exp){

char sym; //to extract each character of the expression.
Stack<Character> st=new Stack<>(); //stack
HashMap<Character,Integer> priority=new HashMap<>(); //store the priority of the operators
priority.put('^',3); //priority of the '^' operator is set 3.
//priority of '*' and '/' are same and are set to 2.
priority.put('*',2);
priority.put('/',2);
//priority of '+' and '-' are same and are set to 1.
priority.put('+',1);
priority.put('-',1);
for(int i=0;i<exp.length();i++){
sym=exp.charAt(i);
if(sym=='(')
st.push(sym);
else{
if(Character.isLetterOrDigit(sym))
System.out.print(sym);
else{
if(sym==')'){
while(st.peek()!='(')
System.out.print(st.pop());
st.pop();
}
else{
while(st.size()>0 && st.peek()!='(' && priority.get(sym)<=priority.get(st.peek()))
System.out.print(st.pop());
st.push(sym);
}
}
}
}
//printing the remaining elements in the Stack
while (st.size()>0)
System.out.print(st.pop());
}
public void expression_tree(String exp){
char[] charArray = exp.toCharArray();
Node root = constructTree(charArray);
inorder(root);

}
Node constructTree(char postfix[]) {
Stack<Node> st = new Stack<Node>();
Node t, t1, t2;

// Traverse through every character of input expression
for (int i = 0; i < postfix.length; i++) {

// If operand, simply push into stack
if (!isOperator(postfix[i])) {
t = new Node(postfix[i]);
st.push(t);
}
else{ // operator
  
t = new Node(postfix[i]);

// Pop two top nodes
// Store top
t1 = st.pop(); // Remove top
t2 = st.pop();

// make them children
t.right = t1;
t.left = t2;

// System.out.println(t1 + "" + t2);
// Add this subexpression to stack
st.push(t);
}
}

// only element will be root of expression tree
t = st.peek();
st.pop();

return t;
}
boolean isOperator(char c) {
if (c == '+' || c == '-'|| c == '*' || c == '/'|| c == '^') {
return true;
}
return false;
}

// Utility function to do inorder traversal
void inorder(Node t) {
if (t != null) {
inorder(t.left);
System.out.print(t.value + " ");
inorder(t.right);
}
}
void evaluate_exp(String exp){
char[] tokens = expression.toCharArray();
  
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
  
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
  
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
  
// Current token is a number, push it to stack for numbers
if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
  
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
  
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
while (ops.peek() != '(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
  
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
  
// Entire expression has been parsed at this point, apply remaining ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  
// Top of 'values' contains result, return it
return values.pop();
}
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
  
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
}

Likes: 0

Dislikes: 0