Help With Data Structure Program CS 372 Infix to Postfix & Evaluation Program Yo

Question

Help With Data Structure Program

CS 372

Infix to Postfix & Evaluation Program

     You are to implement a program that converts an infix expression into a postfix expression and then evaluate the postfix expression. You are to use the Stack and Queue classes you developed with your last assignment where Stack and Queue use your List class to manage the data in the stack and queue.

Output:

     Print out the infix expression, the postfix expression and the calculated results of the expression.

     You are to handle the (), + - * / and ^ (exponential/power) operators. The ^ operator precedence is higher than * and / operators.

Turn in to me the program and the resulting output.

     To test your program, use the following input expressions. Put the input data into a file to be read in. Test your program with some simple expressions before using the data below and make sure each of your operations work correctly.

5 + 7

6 ^ 2 + 1

3 * 8 + 6

5 ^ 4 - 6 ^ 4

5 - 3 * 7 / 4 - 9

8 * ( 9 / 3 - 2 ) / 4 + 5 * 6

5 ^ 3 * 4 + ( 2 + ( 9 * 8 / ( 2 * 6 * ( 8 / 4 ) ) ) ^ 2 * 8 - 5 ) / 5 ^ 2 - 4

5 - 3 * 8 / 2 ^ 3

3 ^ 3 ^ 2 *3

8 * ( 6 / 3 - 2 ) / 4 + 5 * 6 +3

( ( ( ( ( 9 * 5 ) ) ) ) )

Explanation / Answer

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class SampleInfixToPostfix {

   public static void main(String[] args) throws FileNotFoundException {
         
       //Test 1:
       //enter an expression in Infix : 1 * ( 12 + 23 ) - ( 4 / 5 )
       //PostFix form : 1 12 23 + * 4 5 / -

       //Test 2:
       //enter an expression in Infix : 100 * ( 2 + 12 )
       //PostFix form :100 2 12 + *
       File file = new File("infixexp.txt");
Scanner scanner = new Scanner(file);
int i=1;
       while(scanner.hasNext()){
         
           System.out.println("Expression "+i++);
   String infix = scanner.nextLine();
   System.out.println("inFix form :"+infix);
   String postfix = convert(infix);
   System.out.println("PostFix form :"+postfix);
  
   int result=evaluatePostfix(postfix.split(" "));
   System.out.println("postFix Expression Evaluation : "+result);
       }
   }

     
   public static int evaluatePostfix(String[] expr) {
       Stack<Integer> nums = new Stack<Integer>();
       for(int i = 0; i < expr.length; i++) {
       String elt = expr[i];
       if(elt.equals("+")) {
       int b = nums.pop().intValue();
       int a = nums.pop().intValue();
       nums.push(new Integer(a + b));
       } else if(elt.equals("-")) {
       int b = nums.pop().intValue();
       int a = nums.pop().intValue();
       nums.push(new Integer(a - b));
       } else if(elt.equals("*")) {
       int b = nums.pop().intValue();
       int a = nums.pop().intValue();
       nums.push(new Integer(a * b));
       } else if(elt.equals("/")) {
       int b = nums.pop().intValue();
       int a = nums.pop().intValue();
       nums.push(new Integer(a / b));
       }else if(elt.equals("^")) {
       int b = nums.pop().intValue();
       int a = nums.pop().intValue();
       nums.push(new Integer(a ^ b));
       } else { // it must be a number
       int x = Integer.parseInt(elt);
       nums.push(new Integer(x));
       }
       }
       return nums.pop().intValue();
       }
   /**
   * Perform the conversion
   *
   * @param expression Arithmetic infix format
   */
   public static String convert(String expression) {
   // Use StringBuilder to append string is faster than
   // String concatenation
   StringBuilder sb = new StringBuilder();

   // Use a stack to track operations
   Stack<Character> op = new Stack<Character>();

   // Convert expression string to char array
   char[] chars = expression.toCharArray();

   // The length of expression character
   int N = chars.length;

   for (int i = 0; i < N; i++) {
   char ch = chars[i];

   if (Character.isDigit(ch)) {
   // Number, simply append to the result
   while (Character.isDigit(chars[i])) {
   sb.append(chars[i++]);
   }
   // Use space as delimiter
   sb.append(' ');
   } else if (ch == '(') {
   // Left parenthesis, push to the stack
   op.push(ch);
   } else if (ch == ')') {
   // Right parenthesis, pop and append to the result until meet the left parenthesis
   while (op.peek() != '(') {
   sb.append(op.pop()).append(' ');
   }
   // Don't forget to pop the left parenthesis out
   op.pop();
   } else if (isOperator(ch)) {
   // Operator, pop out all higher priority operators first and then push it to the stack
   while (!op.isEmpty() && priority(op.peek()) >= priority(ch)) {
   sb.append(op.pop()).append(' ');
   }
   op.push(ch);
   }
   }

   // Finally pop out whatever left in the stack and append to the result
   while(!op.isEmpty()) {
   sb.append(op.pop()).append(' ');
   }

   return sb.toString();
   }

   /**
   * Check if a character is an operator
   */
   private static boolean isOperator(char ch) {
   return ch == '^' || ch == '*' || ch == '/' || ch == '+' || ch == '-';
   }

   /**
   * Define the operator priority
   */
   private static int priority(char operator) {
   switch (operator) {
   case '^' : return 3;
   case '*' :
   case '/' : return 2;
   case '+' :
   case '-' : return 1;
   }
   return 0;
   }
}

Expression text file ;

5 + 7
6 ^ 2 + 1
3 * 8 + 6
5 ^ 4 - 6 ^ 4
5 - 3 * 7 / 4 - 9
8 * ( 9 / 3 - 2 ) / 4 + 5 * 6
5 ^ 3 * 4 + ( 2 + ( 9 * 8 / ( 2 * 6 * ( 8 / 4 ) ) ) ^ 2 * 8 - 5 ) / 5 ^ 2 - 4
5 - 3 * 8 / 2 ^ 3
3 ^ 3 ^ 2 *3
8 * ( 6 / 3 - 2 ) / 4 + 5 * 6 +3
( ( ( ( ( 9 * 5 ) ) ) ) )

Output :

Expression 1
inFix form :5 + 7
PostFix form :5 7 +
postFix Expression Evaluation : 12
Expression 2
inFix form :6 ^ 2 + 1
PostFix form :6 2 ^ 1 +
postFix Expression Evaluation : 5
Expression 3
inFix form :3 * 8 + 6
PostFix form :3 8 * 6 +
postFix Expression Evaluation : 30
Expression 4
inFix form :5 ^ 4 - 6 ^ 4
PostFix form :5 4 ^ 6 4 ^ -
postFix Expression Evaluation : -1
Expression 5
inFix form :5 - 3 * 7 / 4 - 9
PostFix form :5 3 7 * 4 / - 9 -
postFix Expression Evaluation : -9
Expression 6
inFix form :8 * ( 9 / 3 - 2 ) / 4 + 5 * 6
PostFix form :8 9 3 / 2 - * 4 / 5 6 * +
postFix Expression Evaluation : 32
Expression 7
inFix form :5 ^ 3 * 4 + ( 2 + ( 9 * 8 / ( 2 * 6 * ( 8 / 4 ) ) ) ^ 2 * 8 - 5 ) / 5 ^ 2 - 4
PostFix form :5 3 ^ 4 * 2 9 8 * 2 6 * 8 4 / * / 2 ^ 8 * + 5 - 5 2 ^ / + 4 -
postFix Expression Evaluation : 20
Expression 8
inFix form :5 - 3 * 8 / 2 ^ 3
PostFix form :5 3 8 * 2 3 ^ / -
postFix Expression Evaluation : -19
Expression 9
inFix form :3 ^ 3 ^ 2 *3
PostFix form :3 3 ^ 2 ^ 3 *
postFix Expression Evaluation : 6
Expression 10
inFix form :8 * ( 6 / 3 - 2 ) / 4 + 5 * 6 +3
PostFix form :8 6 3 / 2 - * 4 / 5 6 * + 3 +
postFix Expression Evaluation : 33
Expression 11
inFix form :( ( ( ( ( 9 * 5 ) ) ) ) )
PostFix form :9 5 *
postFix Expression Evaluation : 45

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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