Informacje o nowych artykułach oraz akcjach edukacyjnych prosto na Twojej skrzynce e-mail!

Minimalna liczba nawiasów przy przekształcaniu wyrażeń z „Odwrotnej Notacji Polskiej” (ONP)

Kod

Znając już działanie całego algorytmu możemy zacząć pisać kod źródłowy. Zacznijmy na początku od funkcji zwracającej priorytety.

Kod funkcji pobierzPriorytet() napisanej w Javie, zwracającej priorytet danego znaku:

static int pobierzPriorytet(String znak)
{
     if(znak.equals("+") || znak.equals("-"))
          return 1;
     else if(znak.equals("*") || znak.equals("/"))
          return 2;
     else if(znak.equals("^"))
          return 3;
     else if(znak.equals("~")) //minus unarny (np. -4, -5 zmienia znak liczby)
          return 4;
     else if(znak.charAt(0) >= 'a' && znak.charAt(0) <= 'z') //dla uproszczenia przyjmujemy, że liczby będą reprezentować litery
          return 5;
     
     return 0; //jeśli doszło do błędu		
}

Jak widać nie ma tutaj nic skomplikowanego, po prostu zwracamy odpowiedni priorytet w zależności od podanego jako argument znaku.

Funkcja konwertująca wyrażenia z ONP do INF z minimalną liczbą nawiasów:

    static void doINF(String[] wejscie)
    {
        stackArray stos = new stackArray(wejscie.length);
        stackArrayInt stosPriorytetow = new stackArrayInt(wejscie.length);

        String tmp = "";
        int liczbaOperandow = 0, liczbaOperatorow = 0;

        for(int j = 0;j<wejscie.length;j++)
        {
            if(!wejscie[j].equals("(") && !wejscie[j].equals(")"))
                if(wejscie[j].charAt(0) >= 'a' && wejscie[j].charAt(0) <= 'z')
                {
                    stos.push(wejscie[j]);//element jest operandem
                    stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
                    liczbaOperandow++;
                }
                else
                {
                    tmp = "";

                    if(!wejscie[j].equals("~"))
                    {
                        liczbaOperatorow++;

                        if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
                            tmp = "(" + stos.pop() + ")";
                        else
                            tmp = stos.pop();

                        stosPriorytetow.pop();

                        if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
                            tmp = "(" + stos.pop() + ")" + wejscie[j] + tmp;
                        else
                            tmp = stos.pop() + wejscie[j] + tmp;

                        stosPriorytetow.pop();
                    }
                    else
                    {
                        if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
                            tmp = wejscie[j] + "(" + stos.pop() + ")";
                        else
                            tmp = wejscie[j] + stos.pop();

                        stosPriorytetow.pop();
                    }

                    stos.push(tmp);
                    stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
                }
        }

        if(liczbaOperandow - 1 == liczbaOperatorow)
            System.out.println("<INF>" + stos.pop());
        else
            System.out.println("Podałeś błędne dane!");
    }

Funkcja main:

public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        String dane = "";
        dane = s.nextLine();

        String tab[] = new String[256];

        for(int x = 0;x<dane.length();x++)
            tab[x] = Character.toString(dane.charAt(x));

        int l = 0;

        for(int j = 0;j<tab.length;j++)
            if(tab[j] != null)
                l++;

        String wejscie[] = new String[l]; //musimy mieć tablicę dokładnie takiej samej długości jak wprowadzony string
        for(int j = 0;j<l;j++)
            wejscie[j] = tab[j];

        doINF(wejscie); //konwersja
    }

Do tego dorobić trzeba jeszcze stos, co szczegółowo opisałem w artykule „Abstrakcyjne struktury danych: Stos„.

Jeżeli ktoś miałby z tym problem to poniżej publikuję cały kod:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        String dane = "";
        dane = s.nextLine();

        String tab[] = new String[256];

        for(int x = 0;x<dane.length();x++)
            tab[x] = Character.toString(dane.charAt(x));

        int l = 0;

        for(int j = 0;j<tab.length;j++)
            if(tab[j] != null)
                l++;

        String wejscie[] = new String[l]; //musimy mieć tablicę dokładnie takiej samej długości jak wprowadzony string
        for(int j = 0;j<l;j++)
            wejscie[j] = tab[j];

        doINF(wejscie); //konwersja
    }

    static int pobierzPriorytet(String znak)
    {
        if(znak.equals("+") || znak.equals("-"))
            return 1;
        else if(znak.equals("*") || znak.equals("/"))
            return 2;
        else if(znak.equals("^"))
            return 3;
        else if(znak.equals("~")) //minus unarny (np. -4, -5 zmienia znak liczby)
            return 4;
        else if(znak.charAt(0) >= 'a' && znak.charAt(0) <= 'z') //dla uproszczenia przyjmujemy, że liczby będą reprezentować litery
            return 5;

        return 0; //jeśli doszło do błędu
    }

    static void doINF(String[] wejscie)
    {
        stackArray stos = new stackArray(wejscie.length);
        stackArrayInt stosPriorytetow = new stackArrayInt(wejscie.length);

        String tmp = "";
        int liczbaOperandow = 0, liczbaOperatorow = 0;

        for(int j = 0;j<wejscie.length;j++)
        {
            if(!wejscie[j].equals("(") && !wejscie[j].equals(")"))
                if(wejscie[j].charAt(0) >= 'a' && wejscie[j].charAt(0) <= 'z')
                {
                    stos.push(wejscie[j]);//element jest operandem
                    stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
                    liczbaOperandow++;
                }
                else
                {
                    tmp = "";

                    if(!wejscie[j].equals("~"))
                    {
                        liczbaOperatorow++;

                        if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
                            tmp = "(" + stos.pop() + ")";
                        else
                            tmp = stos.pop();

                        stosPriorytetow.pop();

                        if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
                            tmp = "(" + stos.pop() + ")" + wejscie[j] + tmp;
                        else
                            tmp = stos.pop() + wejscie[j] + tmp;

                        stosPriorytetow.pop();
                    }
                    else
                    {
                        if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
                            tmp = wejscie[j] + "(" + stos.pop() + ")";
                        else
                            tmp = wejscie[j] + stos.pop();

                        stosPriorytetow.pop();
                    }

                    stos.push(tmp);
                    stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
                }
        }

        if(liczbaOperandow - 1 == liczbaOperatorow)
            System.out.println("<INF>" + stos.pop());
        else
            System.out.println("Błędne dane...");
    }
}

class stackArray
{
    private int maxSize;
    private String[] Elem;
    private int top;

    public stackArray(int size)
    {
        maxSize = size;

        Elem = new String[maxSize];
        top = maxSize;
    }

    public void push(String x)
    {
        if(!isFull())
            Elem[--top] = x;
    }

    public String pop()
    {
        if(isEmpty())
            return "";
        else
            return Elem[top++];
    }

    public String top()
    {
        if ( isEmpty() )
            return "";
        else
            return Elem[top];
    }

    public boolean isEmpty()
    {
        return (top == maxSize);
    }

    public boolean isFull()
    {
        return (top == 0);
    }
}

class stackArrayInt
{
    private int maxSize;
    private int[] Elem;
    private int top;

    public stackArrayInt(int size)
    {
        maxSize = size;

        Elem = new int[maxSize];
        top = maxSize;
    }

    public void push(int x)
    {
        if(!isFull())
            Elem[--top] = x;
    }

    public int pop()
    {
        if(isEmpty())
            return 0;
        else
            return Elem[top++];
    }

    public int top()
    {
        if ( isEmpty() )
            return 0;
        else
            return Elem[top];
    }

    public boolean isEmpty()
    {
        return (top == maxSize);
    }

    public boolean isFull()
    {
        return (top == 0);
    }
}

Strony: 1 2 3 4

Spodobało się?

Jeśli tak, to zarejestruj się do newslettera aby otrzymywać informacje nowych artykułach oraz akcjach edukacyjnych. Gwarantuję 100% satysfakcji i żadnego spamowania!

, , , , , , ,

Dodaj komentarz

Odpowiedz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Pin It on Pinterest