1   import java.util.Scanner;
2   /**
3    * 183.592 Programmierpraxis TU Wien WS2014/15 H.Moritsch
4    * Rechnen mit Umgekehrt Polnischer Notation (UPN) 
5    * mit einem Stack-Speicher: die Ausführung einer Operation 
6    * nimmt die zwei obersten Elemente vom Stack, verknüpft 
7    * diese, und legt das Ergebnis wieder auf den Stack.
8    * z. B. (3+6)/4 = 2:
9    *      '3'     legt 3 auf den Stack
10   *      '6'     legt 6 auf den Stack
11   *      '+'     nimmt 6 und danach 3 vom Stack, addiert 
12   *              die beiden, und legt 9 auf den Stack
13   *      '4'     legt 4 auf den Stack
14   *      '/'     nimmt 4 und danach 9 vom Stack, dividiert
15   *              9/4 und legt 2 auf den Stack
16   */
17  public class UPNStack {
18      public static void main(String[] args) {
19          Scanner scanner = new Scanner(System.in);
20  
21          int[] stack;
22  
23          stack = emptystack(10);                     // liefert leeren Stack mit 10 Elementen
24  
25          while (scanner.hasNext()) {
26  
27              if (scanner.hasNextInt()) {
28  
29                  int zahl = scanner.nextInt();       
30      
31                  if (! offerfirst(stack, zahl) )     // "push" zahl 
32                      System.out.println("Stack ist bereits voll");
33              }
34  
35              else {
36  
37                  String s = scanner.next();
38                  char operation = s.charAt(0);       // '+', '-', '*', '/', oder '%'
39  
40                  int operand2 = pollfirst(stack);    // "pop" liefert den zweiten(!) operanden
41                  int operand1 = pollfirst(stack);    // "pop" liefert den ersten operanden
42                  int ergebnis;
43                  
44                  switch ( operation) {
45  
46                      case '+':   ergebnis = operand1 + operand2;
47                      break;
48  
49                      case '-':   ergebnis = operand1 - operand2;
50                      break;
51  
52                      case '*':   ergebnis = operand1 * operand2;
53                      break;
54  
55                      case '/':   ergebnis = operand1 / operand2;
56                      break;
57  
58                      case '%':   ergebnis = operand1 % operand2;
59                      break;
60      
61                      default:    System.out.println("keine gültige Operation");
62                                  ergebnis = -999999;
63                  }
64  
65              System.out.println("=" + ergebnis);
66  
67              offerfirst(stack, ergebnis);        // "push" legt Ergebnis auf den Stack
68              }
69  
70          }   
71  
72      }
73  
74      /**
75      * liefert einen leeren Stack einer bestimmten Kapazität
76      */
77      private static int[] emptystack(int capacity) { 
78          int[] r ;
79          r  = new int[capacity + 1];       // + 0. Element!
80          return r;
81          }
82  
83      /**
84      * Test auf "empty"
85      */
86      private static boolean isempty(int[] stack) {
87          return (stack[0] == 0);     // aktuelle Größe ist 0
88          }
89  
90      /**
91      * liefert aktuelle Größe des Stacks
92      */
93      private static int size(int[] stack) {
94          return stack[0];
95          }
96  
97      /**
98      * Operation "push" 
99      */
100     private static boolean offerfirst(int[] stack, int number) {
101         int i = stack[0];           // aktuelle Größe
102 
103         if (i == stack.length-1)    // Kapazität erreicht
104             return false;
105 
106         i++;                        // um 1 erhöhen
107 
108         stack[i] = number;          // number hinzufügen
109 
110         stack[0] = i;
111         return true;
112     }
113         
114     /**
115     * Operation "pop"
116     */
117     private static int pollfirst(int[] stack) {
118         int i = stack[0];           // aktuelle Größe
119 
120         if (i == 0)                 // Stack ist leer!
121             return -999999;
122         
123         int number = stack[i];      // oberstes (erstes) Element
124 
125         i--;                        // aktuelle Größe um 1 reduzieren
126 
127         stack[0] = i;
128         return number;
129     }
130         
131 }
132