Parity of an Expression
National Olympiad — Municipal round (2018 season)
Submission name: odd.cpp
Problem summary
Determine whether each positive-integer expression containing + and * is even or odd, using ordinary multiplication precedence. Numbers can have many digits.
Input
n, followed by n expression strings without spaces.
Output
One line per expression: 0 for even, 1 for odd.
Constraints
2 ≤ n ≤ 10; each expression has fewer than 100,000 characters.
Worked example
An independently prepared example for this explanation.
Input
2 5+5*6+3 123+6*7*8*9
Output
0 1
Solution analysis
- Only parity matters. A number’s last decimal digit determines its parity, multiplication becomes logical AND, and addition becomes XOR.
- Keep the current product parity and the XOR of completed products. When an operator follows a number, incorporate the number into the product. On +, also finish that product and reset its parity to 1. Append a virtual + to flush the last term.
- For 5+5*6+3, the three product parities are 1,0,1, whose XOR is 0. For 123+6*7*8*9 they are 1 and 0, giving 1. No large integer is ever constructed.
Why it works
After each completed number, product is the parity of all factors in the current multiplication term. At each +, XOR adds exactly that term modulo 2 to the completed sum. Ordinary precedence partitions the expression into precisely these terms, so flushing the last term yields the expression parity.
Watch out. Do not evaluate operations simply left to right. Avoid converting enormous numbers to machine integers. Reset the product to 1, the multiplication identity.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
while(n--){
string expression;
cin>>expression;
expression+='+';
int sum=0;
int product=1;
int number=0;
for(char symbol:expression){
if(symbol>='0'&&symbol<='9'){
number=(symbol-'0')%2;
}
else{
product&=number;
if(symbol=='+'){
// Finish a complete multiplication term.
sum^=product;
product=1;
}
}
}
cout<<sum<<'\n';
}
}