Widzę, że ten kalkulator, krąży po forum, jak jakaś zmora, na wszystkich studiach to dają na zadanie czy co?:)
Jakbym to dostał, to zrobiłbym z nawiasami, bo ewaluowanie wyrażenia jest wtedy banalnie proste (kod za Sedgewick and Wayne):
public class Evaluate
{
public static void main(String[] args)
{
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty())
{ // Read token, push if operator.
String s = StdIn.readString();
if (s.equals("("));
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")"))
{ // Pop, evaluate, and push result if token is ")".
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} // Token not operator or paren: push double value.
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
Oczywiście zakładamy, że mamy stos (swój albo z biblioteki). Algorytm działa, jak widać, prosto:
- Wrzuca (push) operand na stos operandów;
- Wrzuca operator na stos operatorów;
- Ignoruje lewy nawias;
- Jak napotka nawias prawy, to, zrzuca (pop) operator, zrzuca odpowiednią ilość operandów (np. dwa dla dodawania, jeden dla pierwiastka) i wrzuca na stos operandów rezultat z zaaplikowania operatora do operandów (ufffffffff!!:));
Po ostatnim nawiasie prawym, na stosie zostaje jedna wartośc, która jest wartościa, całego wyrażenia.
Jedyny problem jest taki, że wyrażenie musi być "fully parenthesized" (jak to przetłumaczyć - poprawnie nawiasowane/znawiasowane); czyli, na każdy operator dwuargumentowy musi przypadać para nawiasów - lewy i prawy; przed podaniem Stringa kalkulatorowi, lepiej go sformatowac: porozdzielać nawiasy spacjami.
Czyli poprawnym wyrażniem jest: "(2 + (4 * 4))", a nie jest: 4 + 5.
To już trochę za dużo roboty, więc nie wrzucam, ale jets algorytm, który sprawdza poprawność nawiasowania:
- Wyrażenie musi się zaczynać nawiasem lewym lub być liczbą;
- Liczba nawiasów lewych i prawych musi być równa (balanced parenthesis);
- W każdym ciagu zaczynającym sie od nawiasu lewego, liczba nawiasów lewych i prawych jest równa aż do zamykającego go [ten otwierający nawias lewy] nawiasu prawego (to podaję za Kazimierzem Trzęsickim) - Logika Matematyczna dla Informatyków.