|
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 |
// Символы во входном потоке следует вводить через пробел. import java.util.*; import java.lang.*; import java.io.*; class Ideone{ public static void main (String[] args) throws java.lang.Exception{ try{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String line; String a1=""; int st_len=0; Stack<String> st = new Stack(); while( (line = reader.readLine()) != null){ String[] a = line.split(" "); for(int i = 0 ; i < a.length ; i++){ if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){ a1+=a[i]; } else{ if((a[i].equals("+") || a[i].equals("-")) && st_len>0){ for(int j=0; j<2;j++){ if(st_len>0){ if(!st.peek().equals("(")){ a1+=st.pop(); st_len--; } } } } if((a[i].equals("*") || a[i].equals("/")) && st_len>0){ for(int j=0; j<1;j++){ if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){ a1+=st.pop(); st_len--; } } } if(a[i].equals(")") && st_len>0){ for(int j=0; j<=st_len+2;j++){ if(!st.peek().equals("(")){ a1+=st.pop(); st_len--; } } if(st_len!=0){ a1+=st.pop(); st_len--; } } st.push(a[i]); st_len++; } } for(int i = 0 ; i < st_len ; i++){ a1+=st.pop(); } for(int i = 0 ; i < a1.length() ; i++){ if(a1.charAt(i)!='(' && a1.charAt(i)!=')') System.out.print(a1.charAt(i)+" "); } } }catch(IOException ex){ System.err.println("Eror"); } } } |
Алгоритм:
Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты:
1) Если символ не является символом функции или скобкой, добавляем его к выходной строке.
2)
- Если встретили символ функции, помещаем его в стек.
- Если встретили символ функции и при этом стек не пустой, выталкиваем в выходную строку все символы функции, пока не встретим символ, имеющий больший приоритет или открывающую скобку.
- Если символ является закрывающей скобкой:
Выталкиваем элементы из стека в выходную строку, пока верхним элементом стека не станет открывающая скобка. Если после этого на вершине стека находится символ функции, выталкиваем его в выходную строку. - Если символ является открывающей скобкой, помещаем его в стек.
Код на Ideone.