Что такое обратная польская запись можно прочитать в Википедии.
Использовался свой стек, выложенный ранее тут.
Поскольку не было необходимости реализовывать дополнительные функции, то то я обошелся для хранения переменных одним стеком и одной строкой, в отличии от реализации моей коллеги.
Лексемы по сути те же самые, только нет ни слова про функции. Для вычисления строки была сложность в нахождении «числовых значений». Для это бралась подстрока данной строки от начала числа до пробела после него.
|
|
|
||||||
|
|
|
||||||
|
|
|
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
import java.util.Scanner; import java.util.StringTokenizer; /** * Created by green on 20.12.15. */ class Parser{ private String operators = "u+-*/"; private String delimiters = operators + "( )"; public boolean correct = true; private boolean isOperator(String x){ if(x.length() != 1) return false; for(int i = 0; i < operators.length(); i++){ if(x.charAt(0) == operators.charAt(i)) return true; } return false; } private boolean isDelimiter(String x){ if(x.length() != 1) return false; for(int i = 0; i < delimiters.length(); i++){ if(x.charAt(0) == delimiters.charAt(i)) return true; } return false; } private int priority(String x) { if (x.equals("(")) return 1; if (x.equals("+") || x.equals("-")) return 2; if (x.equals("*") || x.equals("/")) return 3; return 4; } public String parse(String infix) { String postfix = ""; steck stack = new steck(); StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true); String prev = "", curr = ""; while (tokenizer.hasMoreTokens()) { curr = tokenizer.nextToken(); if (!tokenizer.hasMoreTokens() && isOperator(curr)) { postfix = ("Некорректное выражение."); correct = false; return postfix; } if (curr.equals(" ")) continue; if (isDelimiter(curr)) { if (curr.equals("(")) stack.push(curr); else if (curr.equals(")")) { while (!stack.peek().equals("(")) { postfix += stack.pop().toString() + " "; if (stack.isEmpty()) { postfix = ("Скобки не согласованы."); correct = false; return postfix; } } stack.pop(); }else { if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) { curr = "u"; }else{ while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek().toString()))) { postfix += stack.pop().toString() + " "; } } stack.push(curr); } }else { postfix += curr + " "; } prev = curr; } while (!stack.isEmpty()) { if (isOperator(stack.peek().toString())) postfix += stack.pop().toString() + " "; else { postfix = "Скобки не согласованы."; correct = false; return postfix; } } return postfix; } public int calc(String postfix) { if(!correct) return 0; steck stack = new steck(); for (int i = 0; i < postfix.length() ; i++) { if(postfix.charAt(i) == ' ') continue; if (postfix.charAt(i) == '+') stack.push(Integer.valueOf(stack.pop().toString()) + Integer.valueOf(stack.pop().toString())); else if (postfix.charAt(i) == '-') { int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString()); stack.push(a - b); } else if (postfix.charAt(i) == '*') stack.push(Integer.valueOf(stack.pop().toString()) * Integer.valueOf(stack.pop().toString())); else if (postfix.charAt(i) == '/') { int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString()); stack.push(a / b); } else if (postfix.charAt(i) == 'u') stack.push(-Integer.valueOf(stack.pop().toString())); else{ int g = postfix.indexOf(' ',i); stack.push(Integer.valueOf(postfix.substring(i, g))); i = g; } } return Integer.valueOf(stack.pop().toString()); } } public class postfix { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = "15 * -(3 - 4)"; Parser x = new Parser(); s = x.parse(s); if(x.correct){ System.out.println(s); System.out.println(x.calc(s)); }else{ System.out.println("Ошибка:"+s); } } } |
Засчитано.