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);
}
}