1106. 解析布尔表达式

题目:

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

“t”，运算结果为 True
“f”，运算结果为 False
“!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
“&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 与的运算（AND）
“|(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 或的运算（OR）

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/parsing-a-boolean-expression
 

解题思路:

对于这种表达式解析问题，我们可以使用栈来辅助解决。

从左到右遍历表达式 expression，对于遍历到的每个字符 cc：

如果 cc 是 “tf!&|” 中的一个，我们直接将其入栈；
如果 cc 是右括号 ‘)’，我们将栈中元素依次出栈，直到遇到操作符 ‘!’ 或 ‘&’ 或 ‘|’。过程中我们用变量 tt 和 ff 记录出栈字符中 ‘t’ 和 ‘f’ 的个数。最后根据出栈字符的个数和操作符计算得到新的字符 ‘t’ 或 ‘f’，并将其入栈。
遍历完表达式 expression 后，栈中只剩下一个字符，如果是 ‘t’，返回 true，否则返回 false。

代码:

(Java)

class Solution {
	    public boolean parseBoolExpr(String expression) {
         var stack = new ArrayDeque<Character>();
        
         for(char c:expression.toCharArray()) {
        	 if(c!='('&&c!=')'&& c!=',') {  //将操作数与操作符放入栈
        		 stack.push(c);
        	 }
        	 if(c == ')') {
        		 int tnum =0 ,fnum = 0;  //统计't'与'f'的个数,方便后面的计算
        		 while(stack.peek()=='f' || stack.peek() == 't') {
        			 if(stack.peek() == 'f') {
        				 fnum++;
        				 stack.pop();
        			 }else {
						tnum++;
						stack.pop();
					}
        		 }
        		 char opt = stack.pop();
            	 char res = 'f';  //计算
            	 if((opt =='!'&& fnum>0) || (opt == '&')&& fnum==0 || (opt == '|')&&tnum>0) {
            		 res = 't';
            	 }
            	 stack.push(res);  //计算结果放入栈中
        	 }
        	 
         }
         return stack.peek() =='t';//最后栈中只会剩下一个,即结果
	    }
	}

C++:

class Solution {
public:
	bool parseBoolExpr(string expression) {
		deque<char> stack;
		for (char c : expression) {
			if (c != '(' && c != ')' && c != ',') {
				stack.push_back(c);
			}
			else if (c == ')') {
				int tnum = 0, fnum = 0;
				while (stack.back() == 'f' || stack.back() == 't') {
					if (stack.back() == 'f') {
						fnum++;
						stack.pop_back();
					}
					else {
						tnum++;
						stack.pop_back();
					}
				}
				char opt = stack.back();
				stack.pop_back();
				char res = 'f';
				if ((opt == '!' && fnum > 0) || (opt == '&' && fnum == 0) || (opt == '|' && tnum > 0)) {
					res = 't';
				}
				stack.push_back(res);
			}
		}

		return stack.back() == 't';
	}
};

今天的文章1106. 解析布尔表达式分享到此就结束了，感谢您的阅读。