[递归和栈] Boolean Expressions

2024-06-19 03:52
文章标签 递归 boolean expressions

本文主要是介绍[递归和栈] Boolean Expressions,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next:

Expression: ( V | V ) & F & ( F | V )


where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed.

To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file.

输入

The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown.

The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below.

输出

For each test expression, print "Expression " followed by its sequence number, ": ", and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line.

Use the same format as that shown in the sample output shown below.

样例输入

( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))

样例输出

Expression 1: F
Expression 2: V
Expression 3: V
解题分析

其实这种表达式的求值可以用两个栈的做法来做,而且某种程度上也更符合思维的一个逻辑。首先,我们定义两个栈来辅助我们表达式的计算,一个栈用来存储数值,一个栈用来存储运算符。接着,我们开始遍历整个表达式,如果遇见了正括号,我们往运算符的栈里扔一个0,如果遇见了反括号,我们先判断栈里有没有元素以及上一个运算符是不是0(如果是0说明我们在上面的运算过程中没有&或者|运算需要我们去处理,所以不用calculate),否则调用calculate函数不断地计算括号里面的值。最后,我们重新insert一下防止括号外边有一些!运算符。当我们遇见"!"的时候,往符号运算符栈里面扔3,当我们遇见&的时候,这个时候我们可以先计算一下同级的&运算符了,然后再往符号运算符里面扔2,同理当我们遇见|的时候,这个时候我们可以先计算一下同级的|运算符了,然后再往符号运算符里面扔1,遇见'F'和'V'的时候,直接往值运算栈里面扔0/1即可。在这样一个双栈过程中,我们确保了!运算符优先级最高,&第二,|第三。最后,我们看看符号运算栈里还有没有元素,如果有的话继续计算即可。

代码实现
#include <iostream>
#define MAXN 110
using namespace std;
int val[MAXN],op[MAXN],vtop=0,otop=0;void insert(int x){while(otop && op[otop-1]==3){x=!x; otop--;}val[vtop++]=x;
}void calculate(){int a=val[--vtop];int b=val[--vtop];int c=op[--otop];if(c==2) insert(a&b);else insert(a|b);
}int main(){string s;int t=0;while(getline(cin,s)){t++;otop=vtop=0;int lens=s.size();for(int i=0;i<lens;i++){switch (s[i]) {case '(':op[otop++]=0;break;case ')':while(otop && op[otop-1]!=0) calculate();--otop;insert(val[--vtop]);break;case '!':op[otop++]=3;break;case '&':while(otop && op[otop-1]>=2) calculate();op[otop++]=2;break;case '|':while(otop && op[otop-1]>=1) calculate();op[otop++]=1;break;case 'V':insert(1);break;case 'F':insert(0);break;default:break;}}while(otop) calculate();cout<<"Expression "<<t<<": "<<(val[0]?'V':'F')<<endl;}return 0;
}

这篇关于[递归和栈] Boolean Expressions的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1073928

相关文章

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

【UVA】10651-Pebble Solitaire(直接递归或者记忆化)

不知道这个题UVA的数据是怎么的,用2个方法交了,第一次直接递归,第二次记忆化剪枝,时间竟然一样!? 直接郁闷了,简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

HCIA--实验十:路由的递归特性

递归路由的理解 一、实验内容 1.需求/要求: 使用4台路由器,在AR1和AR4上分别配置一个LOOPBACK接口,根据路由的递归特性,写一系列的静态路由实现让1.1.1.1和4.4.4.4的双向通信。 二、实验过程 1.拓扑图: 2.步骤: (下列命令行可以直接复制在ensp) 1.如拓扑图所示,配置各路由器的基本信息: 各接口的ip地址及子网掩码,给AR1和AR4分别配置

Winform中在窗体中的Paint事件中重绘会导致递归问题?

在 WinForms 应用程序中,如果在窗体的 Paint 事件处理程序中不断调用 Invalidate 方法,确实可能会导致递归调用的问题。这是因为每次调用 Invalidate 方法时,都会向消息队列添加一个绘制消息,当消息队列中的绘制消息被处理时,会触发 Paint 事件。如果 Paint 事件处理程序中又调用了 Invalidate,就会形成一个循环,导致递归调用 Paint 事件,这

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

归并排序-非递归实现

归并排序的非递归实现  我们可以把 一个数组 先拆分成 最小单元,这是分, 拆分成最小单元之后,我们对每个最小单元进行一次合并,这是治 最小单元 合并一次之后,我们继续 在上一次合并的基础上拆分,并且合并这是 合 , 直到 整个数组 只被拆成了两部分,在进行最终一次的和   我们画图举个例子 源代码如下,我们的merge的合并函数的参数是  原数组,左侧小数组索引位置开头,左侧小数