package Stacks.UseStacks; import java.util.Scanner; import java.util.Vector; import java.util.Stack; import java.util.EmptyStackException; /* * Äà ñå âúâåäå ñèìâîëåí íèç, êîéòî ñúäúðæà àðèòìåòè÷åí èçðàç, ñúñòîÿù ñå îò * îïåðàíäè - öåëè ÷èñëà è îïåðàöèèòå: +, -, *, / , * äà ñå ïðåîáðàçóâà â îáðàòåí ïîëñêè çàïèñ è äà ñå ïðåñìåòíå ñòîéíîñòòà ìó. */ public class InversePolishNotation { // Êëàñ çà ïðåäñòàâÿíå íà îïåðàöèèòå, êîèòî ñå çàïèñâàò â ñòåêà static enum Operation { BRACE ("(", 10), PLUS ("+", 5), MINUS ("-", 5), MULT ("*", 1), DIV ("/", 1); private final String symbol; private final int priority; Operation(String s, int priority) { this.symbol = s; this.priority = priority; } int priority() { return priority; } public String toString() { return symbol; } } static char lookahead; static Scanner sc = new Scanner(System.in); static String input = sc.nextLine(); static int ind = 0; public static void main(String[] args) { Vector<Object> v = null; try { System.out.println((v = convert()).toString()); // ïðåîáðàçóâàíå â ïîñòôèêñåí çàïèñ } catch(Exception e) { System.out.println(e.toString()); } try { System.out.println(compute(v)); // ïðåñìÿòàíå íà àðèòìåòè÷íèÿ èçðàç } catch(Exception e) { System.out.println(e.toString()); } } // Ìåòîä, êîéòî ïðåîáðàçóâà èíôèêñåí çàïèñ íà àðèòìåòè÷åí èçðàç â ïîñòôèêñåí static Vector<Object> convert() throws Exception { Vector<Object> result = new Vector<Object>(); // Âåêòîð çà ïîëó÷àâàíå íà ðåçóëòàòà Stack<Operation> st = new Stack<Operation>(); // Ñòåê çà âðåìåííî ïàçåíå íà îïåðàöèèòå int val; lookahead = getC(); do { // öèêúë çà ÷åòåíå íà ëåêñåìèòå îò âõîäà if (Character.isDigit(lookahead)){ // ÷åòåíà íà ëåêñåìà - ÷èñëî val = lookahead-'0'; while (Character.isDigit(lookahead=getC())) val = val*10+lookahead-'0'; result.add(new Integer(val)); // äîáàâÿíå íà ÷èñëîòî âúâ âåêòîðà } else { // ÷åòåíå íà ëåêñåìà - îïåðàöèÿ Operation t = null; switch(lookahead) { // äîáàâÿíå íà îïåðàöèÿòà â ñòåêà case '(': st.add(Operation.BRACE); break; case '+': t = Operation.PLUS; insert(t, st, result); break; case '-': t = Operation.MINUS; insert(t, st, result); break; case '*': t = Operation.MULT; insert(t, st, result); break; case '/': t = Operation.DIV; insert(t, st, result); break; case ')' : insertBrace(st, result); break; default: throw new Exception("Error in expression"); } lookahead = getC(); } } while (lookahead != '$'); while(!st.isEmpty()) // ñëåä êðàé íà âõîäíèòå ëåêñåìè, îñòàíàëèòå â ñòåêà îïåðàöèè result.add(st.pop()); // ñå ïðåõâúðëÿò âúâ âåêòîðà return result; } // Ìåòîä çà ïðåñìÿòàíå íà àðèòìåòè÷åí èçðàç, çàäàäåí â îáðàòåí ïîëñêè çàïèñ static double compute (Vector<Object> v) throws Exception { double result = 0; char op; Stack<Number> st = new Stack<Number>(); // Ñòåê çà âðåìåííî ïàçåíå íà îïåðàíäèòå Object o = null; for(int i=0; i < v.size(); i++) { o = v.elementAt(i); // ÷åòåíå íà ïîðåäíàòà ëåêñåìà îò âõîäà if(o instanceof Number) // àêî å ÷èñëî - çàïèñâà ñå â ñòåêà st.push((Number)o); else { double operand1 = 0; double operand2 = 0; try { // àêî å îïåðöèÿ - îò ñòåêà ñå âàäÿò operand2 = ((Number)st.pop()).doubleValue(); // âòîðèÿ è operand1 = ((Number)st.pop()).doubleValue(); // ïúðâèÿ ìó îïåðàíä } catch(EmptyStackException e) {throw new Exception("Wrong Expression");} op = o.toString().charAt(0); switch(op) { // ïðîâåðÿâà ñå êîÿ å îïåðàöèÿòà è ñå èçâúðøâà case '+': result = operand1 + operand2; break; case '-': result = operand1 - operand2; break; case '*': result = operand1 * operand2; break; case '/': result = operand1 / operand2; break; } st.push(new Double(result)); // ðåçóëòàòúò ñå çàïèñâà â ñòåêà } } int numb = 0; // Êîãàòî âõîäíèÿò ïîòîê ñâúðøè while(!st.isEmpty()) { // àêî â ñòåêà èìà òî÷íî åäíî ÷èñëî result = ((Double)st.pop()).doubleValue(); // òîâà å ðåçóëòàòúò îò ïðåñìÿòàíåòî numb++; } if(numb != 1) throw new Exception("Wrong Expression"); return result; } // Ìåòîä, êîéòî âêëþ÷âà ïîðåäíàòà ïðî÷åòåíà îïåðàöèÿ â ñòåêà, êàòî ïúðâî // ïðåõâúðëÿ âñè÷êè îïåðàöèè ñ ïî-âèñîê èëè ðàâåí ïðèîðèòåò îò ñòåêà âúâ âåêòîðà. static void insert(Operation t, Stack<Operation> st, Vector<Object> v) { Operation tt; while(!st.isEmpty()) { tt = st.peek(); if(tt.priority() <= t.priority()) v.add(st.pop()); else break; } st.push(t); } // Ìåòîäúò ñå âèêà ïðè íàëè÷èå íà çàòâàðÿùà ñêîáà âúâ âõîäíèÿ ïîòîê è âîäè äî // ïðåõâúðëÿíå íà âñè÷êè çíàöè çà îïåðàöèè îò ñòåêà âúâ âåêòîðà äî ñðåùàíå íà îòâàðÿùà ñêîáà. // Ñàìàòà îòâàðÿùà ñêîáà íå ñå ïðåõâúðëÿ âúâ âåêòîðà static void insertBrace(Stack<Operation> st, Vector<Object> v) { Operation tt; while(!st.isEmpty()) { tt = st.pop(); if(tt != Operation.BRACE) v.add(tt); else break; } } // Ìåòîä, êîéòî ÷åòå è âðúùà ïîðåäíèÿ ñèìâîë îò âõîäà, ïðè êðàé âðúùà '$' static char getC() { try { while(Character.isWhitespace(input.charAt(ind++))); return input.charAt(ind-1); } catch (Exception e) { return '$'; } } }