逻辑布尔表达式(增加计算前公式语法校验)

怼烎@ 2022-10-06 01:50 344阅读 0赞

*业务场景需要实现一个公式计算器,经过提炼成oj*  
**题目如下:**  
给定一个只包括 ‘(’，’)’，’&’，’|’，‘1’，‘0’ 的字符串 s ，计算该表达式的布尔结果  
**注意:**  
其中 多重 ‘(’，’)’ 需要有计算优先级,先计算括号内部运算  
‘&’ => 且  
‘|’ => 或  
‘1’ => true  
‘0’ => false

返回结果数据类:  
class CalculateResult\{  
public Boolean checkResult;  
public Boolean calculateResult;  
\}

**示例 1：**

输入：s = "((1&1|1&0|1)|(1&1))"
    输出：CalculateResult(checkResult=true, calculateResult=true)

**示例 2：**

输入：s = "((((1&0)|(1|0)&1)|1)|0)"
    输出：CalculateResult(checkResult=true, calculateResult=true)

**示例 3：**

输入：s = "1&1&1|1&0"
    输出：CalculateResult(checkResult=true, calculateResult=false)

**示例 4：**

输入：s = "0&"
    输出：CalculateResult(checkResult=false, calculateResult=null)

**示例 5：**

输入：s = "()1)"
    输出：CalculateResult(checkResult=false, calculateResult=null)

解答思路:

public class MainClassC {
    
        @Test
        public void test(){
    
            System.out.println(doCalculate("((1&1|1&0|1)|(1&1))"));
            System.out.println(doCalculate("((((1&0)|(1|0)&1)|1)|0)"));
            System.out.println(doCalculate("1&1&1|1&0"));
            System.out.println(doCalculate("((1&1|0|1)&(0&(0|1)))"));
            System.out.println(doCalculate("11"));
            System.out.println(doCalculate("0&"));
            System.out.println(doCalculate("()1)"));
    
        }
    
        public CalculateResult doCalculate(String targetStr){
            //运算之前预检
            if (checkBracketsValid(targetStr)){
                return calculate(targetStr);
            }
            return new CalculateResult(false,null);
        }
    
        public CalculateResult calculate(String targetStr){
            if (StringUtils.isEmpty(targetStr)){
                return new CalculateResult(false,null);
            }
            //逻辑表达式
            StringBuilder expression = new StringBuilder();
            //前值位逻辑
            CalculateResult preBol = new CalculateResult();
            //前值位逻辑是否存在开关
            boolean preFlag = false;
            for (int i = 0; i < targetStr.length(); i++) {
                char temp = targetStr.charAt(i);
                //括号分割
                if (temp == BracketsConstant.LEFT_BRACKETS){
                    //计算出当前左括号对应的右括号下标位置
                    int j = findClosing(targetStr.substring(i));
                    //递归到最小集进行计算逻辑表达式
                    preBol = calculate(targetStr.substring(i+1,i+j));
                    if (!preBol.getCheckResult())
                        return preBol;
                    expression.append(TrueAndFalseEnum.code(preBol.getCalculateResult()));
                    i += j;
                    preFlag = true;
                }
                //将当前数值追加至当前逻辑表达式中
                if (preBol != null && preFlag){
                    preFlag = false;
                    continue;
                }
                expression.append(temp);
            }
            final CalculateResult calculateResult = new CalculateResult();
            //校验逻辑表达式语法是否正确
            calculateResult.setCheckResult(checkExpressionGrammar(expression.toString()));
            if (calculateResult.getCheckResult()){
                //计算逻辑表达式结果
                calculateResult.setCalculateResult(calcuteExpression(expression.toString()));
            }
            return calculateResult;
        }
    
        /**
         * 检查表达式语法正确性
         * @param expression
         * @return
         */
        public boolean checkExpressionGrammar(String expression){
            //处理栈
            Stack<Character> stack = new Stack<>();
            //当前是否是非符号位
            boolean currentIsNumBol = false;
            //当前字符前一位是否是符号位
            boolean preSymbolBol = false;
            for (int i = 0; i < expression.length(); i++) {
                final char temp = expression.charAt(i);
                //如果前一位是符号位
                if (preSymbolBol){
                    currentIsNumBol = true;
                }
                //如果前一位是符号位 & 当前是非符号位
                if (preSymbolBol && currentIsNumBol){
                    /**
                     * 出两次栈 判断第二次出栈结果是否为非符号位
                     * 条件不满足情况:
                     * 1:当前栈大小不满足出两次栈  返回false
                     * 2:第二次出栈结果为符号位    返回false
                     */
                    if (!stackPopTwoCheck(stack)){
                        return false;
                    }
                    currentIsNumBol = false;
                    preSymbolBol = false;;
                }
                //如果当前字符为符号位的话 将preSymbolBol设为true 供下次循环使用
                if (SymbolConstant.SYMBOL_SET.contains(temp)){
                    preSymbolBol = true;
                }
                stack.push(temp);
            }
            //如果当前栈大小不等1 说明当前栈中数据语法不正确
            return stack.size() == 1;
        }
    
        private boolean stackPopTwoCheck(Stack<Character> stack){
            if (stack.size()<2)
                return false;
            stack.pop();
            if (SymbolConstant.SYMBOL_SET.contains(stack.pop()))
                return false;
            return true;
        }
    
        /**
         * 校验一个字符串中括号是否合法
         * @param targetStr
         * @return
         */
        public boolean checkBracketsValid(String targetStr) {
            //存放左括号栈
            int isBracketCount = 0;
            Stack<Character> leftStack = new Stack<>();
            for (int i = 0; i < targetStr.length(); i++) {
                char temp = targetStr.charAt(i);
                if (BracketsConstant.ALL_BRACKET_SET.contains(temp))
                    isBracketCount++;
                //左括号压栈
                if (temp == BracketsConstant.LEFT_BRACKETS){
                    leftStack.push(temp);
                }else{
                    //非括号字符过滤
                    if (!BracketsConstant.ALL_BRACKET_SET.contains(temp))
                        continue;
                    //当有右括号但是没有左括号匹配时表达式不成立
                    if (leftStack.isEmpty()){
                        return false;
                    }
                    //左括号出栈
                    final Character pop = leftStack.pop();
                    //左括号出栈字符与映射表中右括号不匹配时表达式不成立
                    if (!(temp == BracketsConstant.BRACKET_MAP.get(pop))){
                        return false;
                    }
                }
            }
            return (leftStack.size()==0) && !(isBracketCount==targetStr.length());
        }
    
    
        /**
         * 删除所有的括号对，并返回右括号的位置
         * @param s
         * @return
         */
        private int findClosing(String s) {
            //level:左括号累加值
            int level = 0, i = 0;
            for (i = 0; i < s.length(); i++) {
                //遇到左括号就累加
                if (s.charAt(i) == BracketsConstant.LEFT_BRACKETS) level++;
                //遇到右括号则累减
                else if (s.charAt(i) == BracketsConstant.RIGHT_BRACKETS) {
                    level--;
                    if (level == 0) break;
                }
            }
            return i;
        }
    
        /**
         * 计算逻辑表达式
         * @param expression
         * @return
         */
        public boolean calcuteExpression(String expression){
            if (expression.length() == 1){  //单个数值时
                final char c = expression.charAt(0);
                if (!SymbolConstant.SYMBOL_SET.contains(c)){
                    return TrueAndFalseEnum.value(c);
                }
            }
            boolean retFlag = false;
            char left = expression.charAt(0);
            char right;
            for (int i = 0; i < expression.length(); i++) {
                final char temp = expression.charAt(i);
                if (SymbolConstant.SYMBOL_SET.contains(temp)){
                    if (i+1<expression.length()){
                        //取出右值
                        right = expression.charAt(i+1);
                        //计算左右逻辑运算结果
                        //获取到计算处理类
                        final CalculateMethod calculateMethod = CalculateFactory.getCalculateMethod(temp);
                        if (calculateMethod == null){
                            System.out.println("获取对应的计算处理类未获取到,对应的符号为:"+temp);
                        }
                        //将计算结果重新赋值
                        left = TrueAndFalseEnum.code(calculateMethod.calculate(TrueAndFalseEnum.value(left), TrueAndFalseEnum.value(right)));
                        //跳一位
                        i++;
                    }else{
                        System.out.println("异常 下标越界异常");
                    }
                }
            }
            retFlag = TrueAndFalseEnum.value(left);
            return retFlag;
        }
    
    
    
    }
    @ToString
    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    class CalculateResult{
        public Boolean checkResult;
        public Boolean calculateResult;
    }
    
    abstract class BracketsConstant{
    
        public static final Character LEFT_BRACKETS = '(';
    
        public static final Character RIGHT_BRACKETS = ')';
    
        public static final Map<Character,Character> BRACKET_MAP = new HashMap<>();
    
        public static final Set<Character> ALL_BRACKET_SET = new HashSet<>();
    
        static {
            BRACKET_MAP.put(BracketsConstant.LEFT_BRACKETS,BracketsConstant.RIGHT_BRACKETS);
            ALL_BRACKET_SET.add(LEFT_BRACKETS);
            ALL_BRACKET_SET.add(RIGHT_BRACKETS);
        }
    
    }
    
    abstract class SymbolConstant{
    
        public static final char AND_SYM = '&';
    
        public static final char OR_SYM = '|';
    
        public static Set<Character> SYMBOL_SET = new HashSet<>();
    
        static {
            SYMBOL_SET.add(AND_SYM);
            SYMBOL_SET.add(OR_SYM);
        }
    
    }
    
    enum TrueAndFalseEnum{
        TRUE('1',true),
        FALSE('0',false);
        private char code;
        private boolean value;
    
        TrueAndFalseEnum(char code, boolean value) {
            this.code = code;
            this.value = value;
        }
    
        public static Character code(boolean value){
            for (TrueAndFalseEnum data : TrueAndFalseEnum.values()) {
                if (data.getValue() == value){
                    return data.code;
                }
            }
            return null;
        }
    
        public static Boolean value(char code){
            for (TrueAndFalseEnum data : TrueAndFalseEnum.values()) {
                if (data.getCode() == code){
                    return data.value;
                }
            }
            return null;
        }
    
    
    
        public char getCode() {
            return code;
        }
    
        public boolean getValue() {
            return value;
        }
    
        public void setCode(char code) {
            this.code = code;
        }
    
        public void setValue(boolean value) {
            this.value = value;
        }
    }
    
    class CalculateFactory{
    
        public static CalculateMethod getCalculateMethod(char symbol){
            switch (symbol){
                case SymbolConstant.AND_SYM:
                    return new AndCalculateMethod();
                case SymbolConstant.OR_SYM:
                    return new OrCalculateMethod();
            }
            return null;
        }
    
    }
    
    interface CalculateMethod{
        Boolean calculate(Boolean left,Boolean right);
    }
    
    class AndCalculateMethod implements CalculateMethod{
    
        @Override
        public Boolean calculate(Boolean left, Boolean right) {
            return left && right;
        }
    }
    
    class OrCalculateMethod implements CalculateMethod{
    
        @Override
        public Boolean calculate(Boolean left, Boolean right) {
            return left || right;
        }
    }