As we all know,the computer is eager to handle the format which is more fit to its progressing structure. There is why RPN exists. For example,if we people caclulate some maths,just like 1+2,we are familiar with this format,but not for computer. The computer is used to handle the result by the math format like 1 2 +, it uses the stack structure,to do this more easily. Just as when it sees +, it begins to pop it ,and finds the two former objects(Integers) to do with the operator +. So, how can we put a format like 1+2 to 1 2 + with programing, this method calls RPN. Ok, let’s show the code now.
First, we make a function to judge is the object opertor like + , - , * , / .
public static boolean isOperator(char ch) { if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { return true; } return false; }Then,we give a function to deal with the mathwork priority, we know , we need to caculate () first of all, and the * , / ,last the + , - . So we can give a number to each of these objects to stand for their priority.
public static int getPriority(char ch) { int level = 0; switch (ch) { case '(': level = 1; break; case '+': case '-': level = 2; break; case '*': case '/': level = 3; break; default: break; } return level; }Then, we make a main method to do our things ,that is the change to RPN. There are some points to deal:
We input a normal format , the program change it to a post one.We judge the input format by each of its component, digit,operator or blanket.The program give an output of our hope RPN. public static void main(String[] args) { int num;//to deal with the string num to int num char c;//stack top char int i;//a pointer to ergodic the string Stack<Character> s = new Stack<>();//a stack to handle the main problem Scanner sc = new Scanner(System.in);//input from keyboard String mid = sc.nextLine(); mid += " ";//it is important,to make the i in the range i = 0; while (i < mid.length()) { if (Character.isDigit(mid.charAt(i))) {//digit object num = 0; do { num = num * 10 + Integer.parseInt(mid.charAt(i) + ""); i++; } while (Character.isDigit(mid.charAt(i))); System.out.print(num + " "); } else if (mid.charAt(i) == '(') {//left blanket lowest priority s.push(mid.charAt(i)); i++; } else if (isOperator(mid.charAt(i))) {//operator use our defined priority if (s.empty()) { s.push(mid.charAt(i));//empty stack do push directly i++; } else { while (!s.empty()) {//not empty decide the priority c = s.peek(); if (getPriority(mid.charAt(i)) <= getPriority(c)) { System.out.print(c + " "); s.pop(); } else { break; } } s.push(mid.charAt(i)); i++; } } else if (mid.charAt(i) == ')') { //right blanket to match the nearlest left blanket,the objects duriing the ( and ) should be sout. while (s.peek() != '(') { System.out.print(s.peek() + " "); s.pop(); } s.pop(); i++; } else { i++; } } while (!s.empty()) { System.out.print(s.peek() + " "); s.pop(); } }Ok,lets run it.
The details here to help understanding the progress.
First object is digit 2,we sout it.2. Stack is empty now, we push * directly
As our rules,( should be pushed into the stack whatever happens.
Digit should be sout.
An operator again, we need to judge the priority because the stack is not empty now.We discoverd that the * > ( ,so do not need to sout anythong before we push the * into the stack, that is to say, we push it directly.
A left blanket again,push it without thinking anything more.
Digit should be sout.
sorry for keep the former digit on the picture, I have deel with the second digit 1 already.
8. Operator + again,because of its higher priority than ( , push it directly without sout anything. 9. Digit should be sout.
Now we see the right blanket, it should be deel with the rule of finding the nearest left blanket and then,sout the objects between them, Easily to find that the objects between them is +,so we sout it.11. The last symbol is ), too. As the same process, we deel with it again. 12. We have done the scan now.But we discovered there is still something in the stack,as the rules, we make it out. 13. That is it.
