Language: C++

#include <string>
#include <vector>
#include <iostream>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

const char *C="()*+-&^|0123456789";

int idx;
string s;
bool flag;

ll number(){
	ll a=0;
	while(idx<s.length() && isdigit(s[idx])) a=10*a+(s[idx++]-'0');
	return a;
}

ll expr(){
	vector<ll> a;
	vector<char> op;
	bool first=true;
	while(idx<s.length() && s[idx]!=')'){
		if(!first){
			if(!strchr("*+-&^|",s[idx])) flag=false;
			op.push_back(s[idx]);
			idx++;
		}
		first=false;

		if(idx==s.length()){
			flag=false;
			return 0;
		}

		if('1'<=s[idx] && s[idx]<='9'){
			a.push_back(number());
		}
		else if(s[idx]=='('){
			idx++;
			a.push_back(expr());
			if(idx==s.length() || s[idx]!=')') flag=false;
			idx++;
		}
		else{
			flag=false;
		}
	}

	if(a.size()!=op.size()+1) flag=false;

	if(!flag) return 0;

	while(!op.empty()){
		if(count(op.begin(),op.end(),'*')>0){
			int i=find(op.begin(),op.end(),'*')-op.begin();
			a[i]*=a[i+1];
			a.erase(a.begin()+i+1);
			op.erase(op.begin()+i);
			continue;
		}
		if(count(op.begin(),op.end(),'+')+count(op.begin(),op.end(),'-')>0){
			int i=min(find(op.begin(),op.end(),'+')-op.begin(),find(op.begin(),op.end(),'-')-op.begin());
			if(op[i]=='+') a[i]+=a[i+1];
			else           a[i]-=a[i+1];
			a.erase(a.begin()+i+1);
			op.erase(op.begin()+i);
			continue;
		}
		if(count(op.begin(),op.end(),'&')>0){
			int i=find(op.begin(),op.end(),'&')-op.begin();
			a[i]&=a[i+1];
			a.erase(a.begin()+i+1);
			op.erase(op.begin()+i);
			continue;
		}
		if(count(op.begin(),op.end(),'^')>0){
			int i=find(op.begin(),op.end(),'^')-op.begin();
			a[i]^=a[i+1];
			a.erase(a.begin()+i+1);
			op.erase(op.begin()+i);
			continue;
		}
		if(count(op.begin(),op.end(),'|')>0){
			int i=find(op.begin(),op.end(),'|')-op.begin();
			a[i]|=a[i+1];
			a.erase(a.begin()+i+1);
			op.erase(op.begin()+i);
			continue;
		}
	}
	return a[0];
}

bool is_valid(const string &s){
	idx=0;
	::s=s;
	flag=true;
	expr();
	if(idx<s.length()) flag=false;
	return flag;
}

ll eval(const string &s){
	idx=0;
	::s=s;
	flag=true;
	return expr();
}

vector<string> next_valid_expr(const string &s){
	int n=s.length();
	vector<string> res;
	rep(i,n+1) rep(j,18) {
		string t=s.substr(0,i)+C[j]+s.substr(i,n-i);
		if(is_valid(t)) res.push_back(t);
	}
	rep(i,n){
		string t=s.substr(0,i)+s.substr(i+1,n-i-1);
		if(is_valid(t)) res.push_back(t);
	}
	return res;
}

int main(){
	while(1){
		int n;
		string s; cin>>n>>s;
		if(n==0) break;

		ll ans=-INF;
		vector<string> S=next_valid_expr(s);
		if(n%2==1){
			rep(i,S.size()) ans=max(ans,eval(S[i]));
		}
		else{
			rep(i,S.size()){
				ll tmp=INF;
				vector<string> T=next_valid_expr(S[i]);
				rep(j,T.size()) tmp=min(tmp,eval(T[j]));
				ans=max(ans,tmp);
			}
		}
		cout<<ans<<endl;
	}

	return 0;
}

Compiler output:
a.cc: In function 'll expr()':
a.cc:31:29: error: 'strchr' was not declared in this scope
   31 |                         if(!strchr("*+-&^|",s[idx])) flag=false;
      |                             ^~~~~~
a.cc:4:1: note: 'strchr' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    3 | #include <iostream>
  +++ |+#include <cstring>
    4 | 
a.cc:61:20: error: 'count' was not declared in this scope
   61 |                 if(count(op.begin(),op.end(),'*')>0){
      |                    ^~~~~
a.cc:62:35: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   62 |                         int i=find(op.begin(),op.end(),'*')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/locale_facets.h:48,
                 from /usr/include/c++/14/bits/basic_ios.h:37,
                 from /usr/include/c++/14/ios:46,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:3:
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:62:35: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   62 |                         int i=find(op.begin(),op.end(),'*')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:68:20: error: 'count' was not declared in this scope
   68 |                 if(count(op.begin(),op.end(),'+')+count(op.begin(),op.end(),'-')>0){
      |                    ^~~~~
a.cc:69:39: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   69 |                         int i=min(find(op.begin(),op.end(),'+')-op.begin(),find(op.begin(),op.end(),'-')-op.begin());
      |                                   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:69:39: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   69 |                         int i=min(find(op.begin(),op.end(),'+')-op.begin(),find(op.begin(),op.end(),'-')-op.begin());
      |                                   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:69:80: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   69 |                         int i=min(find(op.begin(),op.end(),'+')-op.begin(),find(op.begin(),op.end(),'-')-op.begin());
      |                                                                            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:69:80: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   69 |                         int i=min(find(op.begin(),op.end(),'+')-op.begin(),find(op.begin(),op.end(),'-')-op.begin());
      |                                                                            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:76:20: error: 'count' was not declared in this scope
   76 |                 if(count(op.begin(),op.end(),'&')>0){
      |                    ^~~~~
a.cc:77:35: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   77 |                         int i=find(op.begin(),op.end(),'&')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:77:35: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   77 |                         int i=find(op.begin(),op.end(),'&')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:83:20: error: 'count' was not declared in this scope
   83 |                 if(count(op.begin(),op.end(),'^')>0){
      |                    ^~~~~
a.cc:84:35: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   84 |                         int i=find(op.begin(),op.end(),'^')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:84:35: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   84 |                         int i=find(op.begin(),op.end(),'^')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:90:20: error: 'count' was not declared in this scope
   90 |                 if(count(op.begin(),op.end(),'|')>0){
      |                    ^~~~~
a.cc:91:35: error: no matching function for call to 'find(std::vector<char>::iterator, std::vector<char>::iterator, char)'
   91 |                         int i=find(op.begin(),op.end(),'|')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:91:35: note:   '__gnu_cxx::__normal_iterator<char*, std::vector<char> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   91 |                         int i=find(op.begin(),op.end(),'|')-op.begin();
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~