import java.util.Deque;
import java.util.List;
public class IKExpressRPN {
/**
* 思路:
* stack
* opStack
* 1.如果是常量,入stack栈
* 2.如果是括号
* a.如果是左括号,入opStack栈
* b.如果是右括号,依次弹出opStack栈,直到遇到左括号
* 3.如果是操作符
* a.如果opStack栈顶为左括号,入opStack栈
* b.如果opStack栈顶为操作符,则比较优先级
* b1.当前>栈顶,入栈
* b2.当前<=栈顶,依次出栈,直到栈顶为左括号(3a),或者是当前>栈顶
* (可以添加一个标识符号,实现在3里面循环)
*
* 优先级关系为
*
* =====================
* 为什么&& > ||,结果跟ik中的rpn不一样,为什么?
*
*
*
*/
public Deque<ExpressionToken> transferRPN(List<ExpressionToken> list){
Deque<ExpressionToken> stack = new ArrayDeque<>();
Deque<ExpressionToken> opStack = new ArrayDeque<>();
for (ExpressionToken token : list){
if (isInteger(token)){
stack.push(token);
} else if (isParentheses(token)){
if (token.getTokenText().equals("(")){
opStack.push(token);
} else {
boolean doPop = true;
while (doPop && !opStack.isEmpty()){
ExpressionToken top = opStack.pop();
if (!top.getTokenText().equals("(")){
stack.push(top);
} else {
doPop = false;
}
}
}
} else if (isOperator(token)){
if (opStack.isEmpty()){
opStack.push(token);
} else {
boolean doPeek = true;
while (doPeek && !opStack.isEmpty()){
ExpressionToken top = opStack.peek();
if (isParentheses(top)){
if (top.getTokenText().equals("(")){
opStack.push(token);
doPeek = false;
} else {
throw new RuntimeException("error");
}
} else if (isOperator(top)){
Operator topOp = Operator.getOperator(top.getTokenText());
Operator op = Operator.getOperator(token.getTokenText());
if (op.getPriority() > topOp.getPriority()){
opStack.push(token);
doPeek = false;
} else {
stack.push(opStack.pop());
}
} else {
throw new RuntimeException("error");
}
}
while (doPeek && opStack.isEmpty()){
opStack.push(token);
}
}
} else {
throw new RuntimeException("error");
}
}
while (!opStack.isEmpty()){
stack.push(opStack.pop());
}
return stack;
}
/**
* 常量
* @return
*/
public boolean isInteger(ExpressionToken token){
String str = token.getTokenText();
try {
int i = Integer.parseInt(str);
if (i <= Integer.MAX_VALUE){
return true;
}
} catch (Exception e){
return false;
}
return false;
}
/**
* 分隔符
* @param token
* @return
*/
public boolean isParentheses(ExpressionToken token){
String str = token.getTokenText();
if (str.trim().equals("(") || str.trim().equals(")")){
return true;
}
return false;
}
/**
* 操作符
* @param token
* @return
*/
public boolean isOperator(ExpressionToken token){
String str = token.getTokenText();
if (str.trim().equals("||")
|| str.trim().equals("&&")
|| str.trim().equals("!=")
|| str.trim().equals("==")
|| str.trim().equals(">=")
|| str.trim().equals(">")
|| str.trim().equals("<=")
|| str.trim().equals("<")
|| str.trim().equals("-")
|| str.trim().equals("+")
|| str.trim().equals("%")
|| str.trim().equals("*")
|| str.trim().equals("/")
|| str.trim().equals("!")){
return true;
}
return false;
}
public static void main(String[] args) {
List<ExpressionToken> tokeList = new IKExpressRPN().createTokeList();
Deque<ExpressionToken> expressionTokens = new IKExpressRPN().transferRPN(tokeList);
System.out.println(expressionTokens);
}
public List<ExpressionToken> createTokeList(){
//10 > 20 || 30 < 50 && (70 > 80 || 90 > 70)
ExpressionToken token = new ExpressionToken();
token.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token.setTokenText("10");
token.setStartPosition(1);
ExpressionToken token1 = new ExpressionToken();
token1.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token1.setTokenText(">");
token1.setStartPosition(4);
ExpressionToken token2 = new ExpressionToken();
token2.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token2.setTokenText("20");
token2.setStartPosition(6);
ExpressionToken token3 = new ExpressionToken();
token3.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token3.setTokenText("||");
token3.setStartPosition(9);
ExpressionToken token4 = new ExpressionToken();
token4.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token4.setTokenText("30");
token4.setStartPosition(11);
ExpressionToken token5 = new ExpressionToken();
token5.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token5.setTokenText("<");
token5.setStartPosition(1);
ExpressionToken token6 = new ExpressionToken();
token6.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token6.setTokenText("50");
token6.setStartPosition(1);
ExpressionToken token7 = new ExpressionToken();
token7.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token7.setTokenText("&&");
token7.setStartPosition(1);
ExpressionToken token8 = new ExpressionToken();
token8.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token8.setTokenText("(");
token8.setStartPosition(1);
ExpressionToken token9 = new ExpressionToken();
token9.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token9.setTokenText("70");
token9.setStartPosition(1);
ExpressionToken token10 = new ExpressionToken();
token10.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token10.setTokenText(">");
token10.setStartPosition(1);
ExpressionToken token11 = new ExpressionToken();
token11.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token11.setTokenText("80");
token11.setStartPosition(1);
ExpressionToken token12 = new ExpressionToken();
token12.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token12.setTokenText("||");
token12.setStartPosition(1);
ExpressionToken token13 = new ExpressionToken();
token13.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token13.setTokenText("90");
token13.setStartPosition(1);
ExpressionToken token14 = new ExpressionToken();
token14.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token14.setTokenText(">");
token14.setStartPosition(1);
ExpressionToken token15 = new ExpressionToken();
token15.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT);
token15.setTokenText("70");
token15.setStartPosition(1);
ExpressionToken token16 = new ExpressionToken();
token16.setTokenType(ExpressionToken.ETokenType.ETOKEN_TYPE_OPERATOR);
token16.setTokenText(")");
token16.setStartPosition(1);
List<ExpressionToken> list = new ArrayList<>();
list.add(token);
list.add(token1);
list.add(token2);
list.add(token3);
list.add(token4);
list.add(token5);
list.add(token6);
list.add(token7);
list.add(token8);
list.add(token9);
list.add(token10);
list.add(token11);
list.add(token12);
list.add(token13);
list.add(token14);
list.add(token15);
list.add(token16);
return list;
}
}