Blog Archive

Wednesday, September 3, 2014

RPN Calculator - Array Based Stack


When I was a student at University of Santiago of Chile, in my first year, teachers told me to buy a calculator that would help me to solve the problems faster.

So I bought this HP48 scientific calculator... it took me about an hour to understand how did it work!!... you have to put first the terms you want to operate and then choose an operation, in other words, if you want to add 1 and 2 (1 + 2) you need to put 1, then 2 and finally +.

A few months after I found out that this way of calculation had a name:
infix (fixed): regular algebraic notation ( a * b + d )
postfix (RPN): Reverse Polish Notation ( a b * d +)

Today I present you this java code to simulate the process of transforming infix to postfix using "array based stacks":

package rpn;
import javax.swing.JOptionPane;

//  Rational:
//      Data type: operand, operator, group
//      Operators order: ^ > [ * = / ] > [ + = - ]
//      Actions:
//          ): pops the last operator.
//          ^: pushes itself directly on (the stack).
//          *, /: pops bigger operators (if any), then pops one equal operator (if any), then pushes itself on.

//          +, -: pops bigger operators (if any), then pops one equal operator (if any), then pushes itself on. 
//          (: if there is no other it pushes itself on and protects the last operator; when a new operator appears, it just replaces the "(".
//      Opeands: non operator and group chars are considered operands and they all are pushed into the stack.


public class RPN {

    public static String read(String message) { return JOptionPane.showInputDialog(message); }
    public static void write(String message) { JOptionPane.showMessageDialog(null, message); }

    public static void main(String[] args)
    {
        char[] infix = read("Algebraic expresion: ").toCharArray();
        Stack operator = new Stack(infix.length);
        Stack postfix = new Stack(infix.length);
        for(char token : infix)
        {
            switch(token)
            {
                case ')':

                    if(!operator.isEmpty())
                        postfix.push(operator.pop());
                    break;
                case '^':

                    operator.push(token);
                    break;
                case '*':
                case '/':
                    if(!operator.isEmpty() && (operator.pick()=='('))

                    {
                        operator.pop();
                        operator.push(token);
                    }
                    else
                    {
                        while(!operator.isEmpty() && operator.pick()=='^')
                            postfix.push(operator.pop());
                        if(!operator.isEmpty() && (operator.pick()=='*' || operator.pick()=='/'))
                            postfix.push(operator.pop());
                        operator.push(token);
                    }
                    break;
                case '+':
                case '-':
                    if(!operator.isEmpty() && (operator.pick()=='('))
                    {
                        operator.pop();
                        operator.push(token);
                    }
                    else
                    {
                        while(! operator.isEmpty() && (operator.pick()=='^' || operator.pick()=='*' || operator.pick()=='/')) 
                            postfix.push(operator.pop());
                        if(!    operator.isEmpty() && (operator.pick()=='+' || operator.pick()=='-'))
                            postfix.push(operator.pop());
                        operator.push(token);
                    }
                    break;
                case '(':
                    if(!operator.isEmpty())
                        if(operator.pick()=='(')
                            break;
                        else
                            operator.push(token);
                    break;
                default:
                    postfix.push(token);
                    break;
            }
        }
        while(!operator.isEmpty())
            postfix.push(operator.pop());

// from here and on is just printing job
        Stack Invertedpostfix = new Stack(infix.length);
        while(!postfix.isEmpty())
            Invertedpostfix.push(postfix.pop());
        String rpnout = "";
        while(!Invertedpostfix.isEmpty())
            rpnout += Invertedpostfix.pop();
        write(rpnout);
    }
}


// This is the Array based stack class used

public class Stack {
    int top;
    char[] list;
    public Stack(int size){ list = new char[size]; top = -1; }
    public void push(char item){ top++; list[top] = item; }
    public char pop(){ top--; return list[top+1]; }
    public char pick() { return list[top]; }
    public boolean isEmpty(){ return -1 == top; }
}

No comments:

Post a Comment