Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <complex>
#include <cassert>
#include <cctype>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
typedef string::const_iterator State;
int N;
ll inf=2e18;
string op="*+-&^|",nums="0123456789";
map<ll,ll> mp;
ll exp(State &be);
ll num(State &be){
	ll ret=0;
	while(isdigit(*be)){
		ret*=10;
		ret+=*be-'0';
		be++;
	}
	return ret;
}
ll factor(State &be){
	if(*be=='('){
		be++;
		ll ret=exp(be);
		be++;
		return ret;
	}else{
		return num(be);
	}
}
ll a3(State &be){
	ll ret=factor(be);
	while(true){
		if(*be=='*'){
			be++;
			ret*=factor(be);
		}else{
			break;
		}
	}
	return ret;
}
ll a2(State &be){
	ll ret=a3(be);
	while(true){
		if(*be=='+'){
			be++;
			ret+=a3(be);
		}else if(*be=='-'){
			be++;
			ret-=a3(be);
		}else{
			break;
		}
	}
	return ret;
}
ll a1(State &be){
	ll ret=a2(be);
	while(true){
		if(*be=='&'){
			be++;
			ret&=a2(be);
		}else{
			break;
		}
	}
	return ret;
}
ll a0(State &be){
	ll ret=a1(be);
	while(true){
		if(*be=='^'){
			be++;
			ret^=a1(be);
		}else{
			break;
		}
	}
	return ret;
}
ll exp(State &be){
	ll ret=a0(be);
	while(true){
		if(*be=='|'){
			be++;
			ret|=a0(be);
		}else{
			break;
		}
	}
	return ret;
}
ll hash(string s,int k){
	ll ret=0;
	rep(i,s.size()){
		ret*=93;
		ret+=s[i];
	}
	ret*=15;
	ret+=k;
	return ret;
}
ll dfs(string s,int k){
	ll tmp=hash(s,k);
	if(mp.count(tmp)) return mp[tmp];
	if(k==N){
//		show(s);
		State be=s.begin();
		return exp(be);
	}
	ll ret=inf;
	if(k%2==0) ret=-inf;
	rep(i,s.size()){
		bool ok=false;
		if(isdigit(s[i])){
			if( i-1>=0&&isdigit(s[i-1]) ) ok=true;
			else if( i+1<s.size()&&isdigit(s[i+1])&&s[i+1]!='0') ok=true;
		}else if(s[i]!='('&&s[i]!=')'){
			if(isdigit(s[i-1])&&isdigit(s[i+1])) ok=true;
		}
		if(!ok) continue;
		string ns=s;
		ns.erase(i,1);
		ll val=dfs(ns,k+1);
		if(k%2) ret=min(ret,val);
		else ret=max(ret,val);
	}
	rep(i,s.size()+1){
		bool ok=false,ok0=false;
		if( i-1>=0&&isdigit(s[i-1]) ) ok0=true,ok=true;
		else if( i<s.size()&&isdigit(s[i]) ) ok=true;
		if(ok){
			rep(j,10){
				if(j==0&&!ok0) continue;
				string ns=s.substr(0,i)+nums[j]+s.substr(i);
				ll val=dfs(ns,k+1);
				if(k%2) ret=min(ret,val);
				else ret=max(ret,val);
			}
		}
		if(i>0&&i<s.size()&&isdigit(s[i-1])&&isdigit(s[i])&&s[i]!='0'){
			rep(j,6){
				string ns=s.substr(0,i)+op[j]+s.substr(i);
				ll val=dfs(ns,k+1);
				if(k%2) ret=min(ret,val);
				else ret=max(ret,val);
			}
		}
	}
	assert(ret!=inf&&ret!=-inf);
	return mp[hash(s,k)]=ret;
}
int main(){
	while(true){
		string s;
		cin>>N>>s;
		if(N==0) break;
		mp.clear();
		cout<<dfs(s,0)<<endl;
	}
}

Compiler output:
a.cc: In function 'll dfs(std::string, int)':
a.cc:124:16: error: reference to 'hash' is ambiguous
  124 |         ll tmp=hash(s,k);
      |                ^~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:113:4: note:                 'll hash(std::string, int)'
  113 | ll hash(string s,int k){
      |    ^~~~
a.cc:171:19: error: reference to 'hash' is ambiguous
  171 |         return mp[hash(s,k)]=ret;
      |                   ^~~~
/usr/include/c++/14/bits/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:113:4: note:                 'll hash(std::string, int)'
  113 | ll hash(string s,int k){
      |    ^~~~