问题 C: [CSP-J 2022] 逻辑表达式

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路” 
			

				=1
				

					
					

						【数据范围】
					


					

						设 $|s|$ 为字符串 $s$ 的长度。
					

					

						对于所有数据，$1\le |s|\le {10}^6$。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$ 中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表达式）。
					

					

						
						

							
							

								
								

									测试点编号
								

								

									$|s|\le$
								

								

									特殊条件
								

							

						

						

							
							

								
								

									$1\sim 2$
								

								

									$3$
								

								

									无
								

							

							

								
								

									$3\sim 4$
								

								

									$5$
								

								

									无
								

							

							

								
								

									$5$
								

								

									$2000$
								

								

									1
								

							

							

								
								

									$6$
								

								

									$2000$
								

								

									2
								

							

							

								
								

									$7$
								

								

									$2000$
								

								

									3
								

							

							

								
								

									$8\sim 10$
								

								

									$2000$
								

								

									无
								

							

							

								
								

									$11\sim 12$
								

								

									${10}^6$
								

								

									1
								

							

							

								
								

									$13\sim 14$
								

								

									${10}^6$
								

								

									2
								

							

							

								
								

									$15\sim 17$
								

								

									${10}^6$
								

								

									3
								

							

							

								
								

									$18\sim 20$
								

								

									${10}^6$
								

								

									无
								

							

						

					

					

						其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。
					

					

						【提示】
					

					

						以下给出一个“符合规范的逻辑表达式”的形式化定义：
					

					

						
						

							字符串 0 和 1 是符合规范的；
						

						

							如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
						

						

							如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
						

						

							所有符合规范的逻辑表达式均可由以上方法生成。