Infix to Postfix Conversion Using Stacks and Generics.

Infix to postfix conversion takes a formula like 2 + 2 – 1, which is infix, and converts it to postfix: 2 2 + 1 -. taking in account the priority of the operators and associativity between operators. This code convert from infix to postfix and also calculate the total. For that I’m using Stacks and generics. The in put file “datafile.txt” contains the following equation. The “$” sign, signifies the end of equation.
input:
10 + 10 – ( 5 – 5 ) / 2 $
4 * 2 / 4 + 3 $
4 * 4 + 5 $

output
10 10 + 5 5 – 2 / –
20
4 2 * 4 / 3 +
5
4 4 * 5 +
21

code

/*
 * converting from infix to postfix notation
 * using stacks by Jorge L. Vazquez
 */
package tester1;
 
import java.io.*;
import java.util.*;
 
public class Main {
 
    static Stack optor = new Stack();
    static Stack oprand = new Stack();
    static String strOut = "";
    static boolean insideParen = false;
    static boolean isOprand = true;
 
    public static void main(String[] args) throws FileNotFoundException, IllegalArgumentException {
 
        File dataFile = new File("datafile.txt");
 
        Scanner in = new Scanner(dataFile);
 
        while (in.hasNext()) {
            String next = in.next();
            do {
                if (isOperator(next)) {
                    processOptor(next);
                    isOprand = true;
                } else {
                    //throw an exception if there's more than one operand in a row
                    if (isOprand) {
                        oprand.push(Integer.parseInt(next));
                        strOut += next + " ";
                        isOprand = false;
                    } else {
                        throw new IllegalArgumentException("Bad formula!...");
                    }
                }
                next = in.next();
 
                //if reach the end, process operator one last time
                if (next.equals("$")) {
                    processOptor(next);
                }
 
            } while (!next.equals("$"));
 
            System.out.println(strOut);
            System.out.println(oprand.top());
 
            //clearing out string output and all stacks
            strOut = "";
            oprand.pop();
            optor.pop();
            isOprand = true;
        }
    }

    //process operator
    static void processOptor(String op) {
        do {
            if (op.equals("(")) {
                insideParen = true;
                optor.push(op);
                return;
            }
 
            //when find closing parentesis caclculate the numbers and
            //pop out all operators inside perentesis
            if (op.equals(")")) {
                insideParen = false;
                while (!optor.top().equals("(")) {
                    strOut += optor.top() + " ";
                    oprand.push(calculateTotal(optor.top()));
                    optor.pop();
                }
                optor.pop();
                return;
            }
 
            //while inside parentesis keep pushing into stack all operators
            //and keep count of how many operators are inside parentesis
            if (insideParen) {
                optor.push(op);
                return;
            }
            if (!insideParen && optor.isEmpty()) {
                optor.push(op);
                return;
            }
            if (!insideParen && getPriority(op) > getPriority(optor.top())) {
                optor.push(op);
                return;
            }
            if (!insideParen && getPriority(op) == getPriority(optor.top())) {
                if (associativity(getPriority(op)).equals("right")) {
                    optor.push(op);
                    return;
                }
            }
 
            //calculate and push into operand stack
            oprand.push(calculateTotal(optor.top()));
 
            //add operator to string output and pop from stack
            strOut += optor.top() + " ";
            optor.pop();
 
        } while (true);
    }
 
    //calculate total
    static int calculateTotal(String op) {
        int num1, num2;
        num1 = oprand.top();
        oprand.pop();
 
        num2 = oprand.top();
        oprand.pop();
 
        switch (op) {
            case "^":
                return (int) Math.pow(num2, num1);
            case "*":
                return num2 * num1;
            case "/":
                return num2 / num1;
            case "+":
                return num2 + num1;
            case "-":
                return num2 - num1;
            default:
                return -1;
        }
    }
 
    //checking for operators
    public static boolean isOperator(String s) {
        boolean isOptor = false;
        String operator = "-+*/^()";
        if (operator.indexOf(s) != -1) {
            isOptor = true;
        }
        return isOptor;
    }
 
    //returning level of priority
    public static int getPriority(String s) {
        switch (s) {
            case "-":
            case "+":
                return 1;
            case "*":
            case "/":
                return 2;
            case "^":
                return 3;
            default:
                return -1;
        }
    }
 
    //return associativity (left or right)
    public static String associativity(int level) {
        if (level  {
 
    T value;
    Node next;
 
    //constructor
    public Node(T a) {
        value = a;
        next = null;
    }
}
 
class Stack {
 
    public Node head;
 
    //constructor
    public Stack() {
        head = null;
    }
 
    //adding to stack
    public void push(T a) {
        Node p = new Node(a);
        p.next = head;
        head = p;
    }
 
    //removing from stack
    public void pop() {
        head = head.next;
    }
 
    //getting top element
    public T top() {
        return head.value;
    }
 
    public boolean isEmpty() {
        return head == null;
    }
 
    //dispaly stack
    public void display() {
        if (head == null) {
            System.out.println("Stack is empty!...");
        } else {
            Node s = head;
            while (s != null) {
                System.out.println(s.value);
                s = s.next;
            }
        }
    }
}
Share This!

Leave a Reply

Your email address will not be published.