<!-- TOC -->

• HUAWEI 2019 school written examination - logical calculation

  • Title Description
  • Input description
  • For example:

  • Example 1

    • input
    • output

  • Example 2

    • input
    • output
  • Sample code

<!-- /TOC -->

HUAWEI 2019 school written examination - logical calculation

Title Description

Commonly used logical operations are And (expressed as &), Or (expressed as |), Not (expressed as!), and their logic is:

1&1=1 1&0=0 0&1=0 0&0=0
1|1=1 1|0=1 0|1=1 0|0=0
!0=1 !1=0

Among them, their priority relationship is not (!) > And (&) > Or (|);
For example:

A|B&C the truth is that A(B&C)  
A&B|C&D the truth is that (A&B)|(C&D)  
!A&B|C the truth is that ((!A)&B)|C

Input description

1. There is no space in the middle of the test case, no space need to be considered.
2. Only the following characters will appear in the test case representation:

0,1,(,),&,|,!

3. The input and output of test cases are legitimate. There is no need to consider illegal input.
4. Test case expressions will not exceed 128 characters in length.
5. Brackets can be nested.

For example:

1|(1&0) = 1
1&0|0&1 = 0
!0&1|0 = 1
((!0&1))|0 = 1

Example 1

input

!(1&0)|0&1

output

1

Example 2

input

!(1&0)&0|0

output

0

Sample code

public class Solution {
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        Solution solution = new Solution();
        String postfixExpression = solution.converToPostfix(input);

//        System.out.println(postfixExpression);

        int result = solution.numberCalculate(postfixExpression);
        System.out.println(result);
    }

    //Functions that operate on suffix expressions
    private int numberCalculate(String postfix) throws Exception {
        Stack st = new Stack<>();//Create an operand stack
        for (int i = 0; postfix != null && i < postfix.length(); i++) {
            char c = postfix.charAt(i);
            //If it is an operator
            if (isOperator(c) && !st.isEmpty()) {
                int d3 = 0;

                if (c == '!') {
                    int d1 = Integer.parseInt(st.pop().toString());
                    d3 = d1 == 0 ? 1 : 0;
                } else {
                    int d2 = Integer.parseInt(st.pop().toString());
                    int d1 = Integer.parseInt(st.pop().toString());

                    if ('&' == c) {
                        d3 = d1 & d2;
                    }
                    if ('|' == c) {
                        d3 = d1 | d2;
                    }
                }
                //Push the result of the operation into the operand stack
                st.push(d3);
            } else {
                //Press directly into the operand stack for operands
                st.push(c);
            }
        }
        return (int) st.pop();//Returns the result of the operation
    }

    //Converts an arithmetic expression to a function of a suffix expression, and the result is returned as a string
    private String converToPostfix(String expression) throws Exception {
        Stack<Character> st = new Stack<>();   //Initialize an operator stack
        String postfix = new String();   //Used to store suffix expressions
        for (int i = 0; expression != null && i < expression.length(); i++) {
//            System.out.println(st);
            char c = expression.charAt(i);
            if (' ' != c) {
                //For left bracket
                if (isOpenParent(c)) {
                    st.push(c);
                }//Right brackets
                else if (isCloseParent(c)) {
                    char ac = st.pop();
                    while (!isOpenParent(ac)) {
                        postfix = postfix.concat(String.valueOf(ac));
                        if (!st.empty()) {
                            ac = st.pop();
                        }
                    }
                    //In front of the left bracket, pop!
                    char temp = st.pop();
                    if (temp == '!') {
                        postfix = postfix.concat(String.valueOf(temp));
                    } else {
                        st.push(temp);
                    }

                }//Operator
                else if (isOperator(c)) {
                    //Operating stack is not empty, take out the operator with high priority at the top of stack and send the suffix expression.
                    if (!st.empty()) {
                        char ac = st.pop();
                        //The character priority of stack extraction is higher than that of c.
                        while (!st.isEmpty() && priority(ac) >= priority(c)) {
                            postfix = postfix.concat(String.valueOf(ac));
                            ac = st.pop();
                        }//If the priority of character extracted from stack is lower than that of c, the extracted character will be re-stacked.
                        if (ac != ' ') {
                            st.push(ac);
                        }
                    }
                    st.push(c);    //Stack c
                }//For operands, connect directly to postfix
                else {
                    postfix = postfix.concat(String.valueOf(c));
                }
            }
        }//When the expression is read, add the arithmetic stack pop out to postfix
        while (!st.isEmpty()) {
            postfix = postfix.concat(String.valueOf(st.pop()));
        }
        return postfix;
    }

    //Judging that a character is an operator
    private boolean isOperator(char c) {
        return '!' == c || '&' == c || '|' == c;
    }

    //Judgment character is left bracket
    private boolean isOpenParent(char c) {
        return c == '(';
    }

    //Judge character to be right bracket
    private boolean isCloseParent(char c) {
        return c == ')';
    }

    //Judging the Priority of the Algorithms
    private int priority(char c) {
        if (c == '!') {
            return 3;
        }
        if (c == '&') {
            return 2;
        } else if (c == '|') {
            return 1;
        } else return 0;
    }
}