<!-- TOC -->

<!-- /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``

`1`

## Example 2

### input

``!(1&0)&0|0``

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

Keywords: Java

Added by trufla on Thu, 03 Oct 2019 23:34:26 +0300