当前位置: 首页 > 工具软件 > IKExpression > 使用案例 >

IKexpression解读二

轩辕越泽
2023-12-01

将expressionToken转化为逆波兰式,

其中逆波兰式与计算机中函数调用栈吻合

具体可参考百度百科文章逆波兰式

其中问题:为什么需要将IK中element转化为ExpressionToken?


    /**
     * 两个栈,
     * 一个普通栈,用于存储逆波兰式,
     * 一个是操作符栈,用于存储操作符,并根据操作符的优先级,进行不同的处理
     * 算法可参考栈部分
     * 当前操作符的优先级 > 栈顶操作符的优先级,则继续压栈
     * 当前操作符的优先级 <= 栈顶操作符的优先级,则pop出来,加入到普通栈中,形成逆波兰式
     * 如果是括号,怎么处理,
     * 先处理括号,切括号的优先级最低
     */
    public Deque<ExpressionToken> transferRPN(List<ExpressionToken> list){
        Deque<ExpressionToken> stack = new ArrayDeque<>();
        Deque<ExpressionToken> opStack = new ArrayDeque<>();

        List<ExpressionToken> tokenList = createTokeList();
        for (ExpressionToken token : tokenList){
            if (token.getTokenType() == ExpressionToken.ETokenType.ETOKEN_TYPE_CONSTANT){
                stack.push(token);
            } else {
                if (token.getTokenText().equals("(")){
                    opStack.push(token);
                } else if (token.getTokenText().equals(")")){
                    while (!opStack.isEmpty() && !opStack.peek().getTokenText().equals("(")){
                        stack.push(opStack.pop());
                    }
                    if (opStack.peek().getTokenText().equals("(")){
                        opStack.pop();
                    } else {
                        throw new RuntimeException("error");
                    }
                } else {
                    if (opStack.isEmpty() ||
                            Operator.getOperator(token.getTokenText()).getPriority() > Operator.getOperator(opStack.peek().getTokenText()).getPriority()){
                        opStack.push(token);
                    } else {
                        while (!opStack.isEmpty() && !opStack.peek().getTokenText().equals("(") && !opStack.peek().getTokenText().equals(")")
                        && Operator.getOperator(token.getTokenText()).getPriority() <= Operator.getOperator(opStack.peek().getTokenText()).getPriority()){
                            stack.push(opStack.pop());
                        }
                        opStack.push(token);
                    }
                }
            }
        }

        while (!opStack.isEmpty()){
            stack.push(opStack.pop());
        }
        return stack;
    }


    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;
    }

/**
 * 表达式解析词元对象
 * @author 林良益,卓诗垚
 * @version 2.0 
 * 2008-09-18
 */
public class ExpressionToken {
	

	//词元的语法类型
	public enum ETokenType{
		//常量
		ETOKEN_TYPE_CONSTANT ,
		//变量
		ETOKEN_TYPE_VARIABLE ,	
		//操作符
		ETOKEN_TYPE_OPERATOR ,
		//函数
		ETOKEN_TYPE_FUNCTION ,
//		//分隔符
//		ETOKEN_TYPE_SPLITOR ,
		;
	}
	
	//Token的词元类型:常量,变量,操作符,函数,分割符
	private ETokenType tokenType ;
	//存储字符描述
	private String tokenText ;
	//词元在表达式中的起始位置
	private int startPosition = -1;

	public ETokenType getTokenType() {
		return tokenType;
	}

	public void setTokenType(ETokenType tokenType) {
		this.tokenType = tokenType;
	}

	public String getTokenText() {
		return tokenText;
	}

	public void setTokenText(String tokenText) {
		this.tokenText = tokenText;
	}

	public int getStartPosition() {
		return startPosition;
	}

	public void setStartPosition(int startPosition) {
		this.startPosition = startPosition;
	}

	@Override
	public String toString(){
		return tokenText;
	}
}
    public static void main(String[] args) throws IOException {
//        LevelReader lr = new LevelReader("  10 > 20 || 30 < 50 && (70 > 80 || 90 > 70)");
//        lr.readToken();

        LevelReader lr = new LevelReader(" ");
        List<ExpressionToken> tokeList = lr.createTokeList();
        Deque<ExpressionToken> expressionTokens = lr.transferRPN(tokeList);
        System.out.println(new Gson().toJson(expressionTokens));
    }

 类似资料: