#APS Lab 1/5

Постфикс нотација Problem 1 (0 / 0)

Да се напише алгоритам кој ќе врши евалуација на израз во постфикс нотација.

На влез се чита низа од знаци за изразот (стринг), а на излез се печати вредноста на изразот по евалуацијата.

Име на класата (Java): PostFixEvaluation


==================================================================================================================================

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.NoSuchElementException;

public class PostFixEvaluation {

    static interface Queue<E> {

        // Elementi na redicata se objekti od proizvolen tip.

        // Metodi za pristap:

        public boolean isEmpty ();
        // Vrakja true ako i samo ako redicata e prazena.

        public int size ();
        // Ja vrakja dolzinata na redicata.

        public E peek ();
        // Go vrakja elementot na vrvot t.e. pocetokot od redicata.

        // Metodi za transformacija:

        public void clear ();
        // Ja prazni redicata.

        public void enqueue (E x);
        // Go dodava x na kraj od redicata.

        public E dequeue ();
        // Go otstranuva i vrakja pochetniot element na redicata.

    }

    static class LinkedQueue<E> implements Queue<E> {

        // Redicata e pretstavena na sledniot nacin:
        // length go sodrzi brojot na elementi.
        // Elementite se zachuvuvaat vo jazli dod SLL
        // front i rear se linkovi do prviot i posledniot jazel soodvetno.
        SLLNode<E> front, rear;
        int length;

        // Konstruktor ...

        public LinkedQueue () {
            clear();
        }

        public boolean isEmpty () {
            // Vrakja true ako i samo ako redicata e prazena.
            return (length == 0);
        }

        public int size () {
            // Ja vrakja dolzinata na redicata.
            return length;
        }

        public E peek () {
            // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
            if (front == null)
                throw new NoSuchElementException();
            return front.element;
        }

        public void clear () {
            // Ja prazni redicata.
            front = rear = null;
            length = 0;
        }

        public void enqueue (E x) {
            // Go dodava x na kraj od redicata.
            SLLNode<E> latest = new SLLNode<E>(x, null);
            if (rear != null) {
                rear.succ = latest;
                rear = latest;
            } else
                front = rear = latest;
            length++;
        }

        public E dequeue () {
            // Go otstranuva i vrakja pochetniot element na redicata.
            if (front != null) {
                E frontmost = front.element;
                front = front.succ;
                if (front == null)  rear = null;
                length--;
                return frontmost;
            } else
                throw new NoSuchElementException();
        }

    }

    static class SLLNode<E> {
        protected E element;
        protected SLLNode<E> succ;

        public SLLNode(E elem, SLLNode<E> succ) {
            this.element = elem;
            this.succ = succ;
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }


    static interface Stack<E> {

        // Elementi na stekot se objekti od proizvolen tip.

        // Metodi za pristap:

        public boolean isEmpty ();
        // Vrakja true ako i samo ako stekot e prazen.

        public E peek ();
        // Go vrakja elementot na vrvot od stekot.

        // Metodi za transformacija:

        public void clear ();
        // Go prazni stekot.

        public void push (E x);
        // Go dodava x na vrvot na stekot.

        public E pop ();
        // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
    }

    static class LinkedStack<E> implements Stack<E> {

        //Stekot e pretstaven na sledniot nacin: top e link do prviot jazol
        // na ednostrano-povrzanata lista koja sodrzi gi elementite na stekot .
        private SLLNode<E> top;

        public LinkedStack () {
            // Konstrukcija na nov, prazen stek.
            top = null;
        }

        public boolean isEmpty () {
            // Vrakja true ako i samo ako stekot e prazen.
            return (top == null);
        }

        public E peek () {
            // Go vrakja elementot na vrvot od stekot.
            if (top == null)
                throw new NoSuchElementException();
            return top.element;
        }

        public void clear () {
            // Go prazni stekot.
            top = null;
        }

        public void push (E x) {
            // Go dodava x na vrvot na stekot.
            top = new SLLNode<E>(x, top);
        }

        public E pop () {
            // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
            if (top == null)
                throw new NoSuchElementException();
            E topElem = top.element;
            top = top.succ;
            return topElem;
        }

    }

    public static int evalExpression(char []arr){

        LinkedStack<Integer> stek = new LinkedStack<>();
        LinkedQueue<String>  ispeglana = new LinkedQueue<>();

        String str = "";
        for(int i = 0; i < arr.length; i++){

            if(arr[i] == ' '){
                ispeglana.enqueue(str);
                str = "";
            }else{
                str += arr[i];
            }

        }
        ispeglana.enqueue(str);




        while(!ispeglana.isEmpty()){

            String element = ispeglana.dequeue();

            if(element.equals("+")){
                int a = stek.pop();
                int b = stek.pop();
                b += a;
                stek.push(b);;
            }
            else if(element.equals("-")){
                int a = stek.pop();
                int b = stek.pop();
                b -= a;
                stek.push(b);;

            }
            else if(element.equals("*")){
                int a = stek.pop();
                int b = stek.pop();
                b *= a;
                stek.push(b);;
            }
            else if(element.equals("/")){
                int a = stek.pop();
                int b = stek.pop();
                b /= a;
                stek.push(b);;
            }
            else{
                stek.push(Integer.parseInt(element));
            }

        }


        int x = stek.pop();
        return x;


    }


    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String expression = br.readLine();
        char exp[] = expression.toCharArray();



        System.out.println(evalExpression(exp));



        br.close();

    }

}