package com.yj.rpn;
import java.util.*;
import java.util.logging.StreamHandler;
/**
* Created by yanjie on 17/10/31.
* 逆波兰式
* 使用到的符号
* #
* +-
* *\\/
* () 括号比较特殊
*/
public class RPN {
private Map sy = new HashMap();
public RPN(){
sy.put("#",0);
sy.put("(",0);
sy.put(")",0);
sy.put("+",1);
sy.put("-",1);
sy.put("*",2);
sy.put("/",2);
}
private Stack s1 = new Stack();
private Stack s2 = new Stack();
public String getRpn(String s){
s1.add("#");
Boolean pre = false;
for(int i=0; i
char c = s.charAt(i);
//识别操作数
String t = "";
while(i
t = t + c;
if(++i>=s.length()){
break;
}
c = s.charAt(i);
}
if(!t.equals("")){
s2.add(t);
}
if(i>=s.length()){
break;
}
switch (c){
case '('://取出的字符是“(”，则直接送入S1栈顶
s1.add(c+"");
break;
case ')'://取出的字符是“)”，则将距离S1栈栈顶最近的“(”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“(”
t = s1.pop();
while(!t.equals("(")){
s2.add(t);
t = s1.pop();
}
break;
default:
String s1c = s1.peek();
//当前运算符优先级大于s1栈顶优先级,运算符存入s1
if(sy.get(c+"")>sy.get(s1c)){
s1.add(c+"");
}else{//将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于(不包括等于)该运算符优先级，最后将该运算符送入S1栈
while(sy.get(s1c)>=sy.get(c+"")){
s1c = s1.pop();
s2.add(s1c);
}
s1.add(c+"");
}
}
}
String t = s1.pop();
while(!t.equals("#")){
s2.add(t);
t = s1.pop();
}
String result = "";
while(s2.size()>0){
result = s2.pop() +" "+ result;
}
return result;
}
//main method
public static void main(String[] args) {
RPN rpn = new RPN();
String result = rpn.getRpn("1+2*3");
System.out.println(result);
result = rpn.getRpn("(1+2)*3");
System.out.println(result);
result = rpn.getRpn("(a+cc)*3");
System.out.println(result);
}
}