给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。表达式求值是注意and 的优先级比 or 要高，比如：true or false and false，等价于 true or (false and false)，计算结果是 true。
[编程题]表达式求值
- 热度指数：3047 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
输入第一行包含布尔表达式字符串s，s只包含true、false、and、or几个单词（不会出现其它的任何单词），且单词之间用空格分隔。 (1 ≤ |s| ≤ 103).
输出描述:
输出true、false或error，true表示布尔表达式计算为真，false表示布尔表达式计算为假，error表示一个不合法的表达式。
示例1
输入
and
输出
error
示例2
输入
true and false
输出
false
示例3
输入
true or false and false
输出
true
我觉得这题考虑的有两点：
1.输入格式判断
2.格式正确时,怎么求值
1.可设立计数点，从0开始，逐渐加1，
2k时 输入的只能是false 或 true,
2k+1时，输入的只能是 and 或 or.
考虑到 输入顺序正确但是个数不对，即 false and,所以再加上一个size(false/true)-size(and/or)==1的判断
2.求值的话，就正常地利用栈 ，表达式求值，注意运算符优先级
#include<iostream>
(720)#include<string>
#include<stack>
using namespace std;
string Reduce(string str1,string str2,string op)
{
if(op=="and")
{
if((str1=="true"&& str2=="true"))
return "true";
else return "false";
}
else//o***bsp; {
if(str1=="false"&&str2=="false")
return "false";
else return "true";
}
}
bool Comp(string op1,string op2)//op1:栈外 Op2:栈内 op1>op2 return true
{
if(op1=="and"&&op2=="or")
return true;
else return false;
}
int main()//false&nbs***bsp;true and false&nbs***bsp;true and false
{
string str;
string output;
stack <string> S,OP;
int count=0;
while(cin.peek()!='\n')
{
cin>>str;
if((count%2==0)&&(str=="false"||str=="true"))
S.push(str);
else if((count%2==1)&&(str=="and"||str=="or"))//op
{
if(OP.empty())
OP.push(str);
else
{ while(!OP.empty()&&!Comp(str,OP.top()))
{
string s1,s2,op,output;
s1=S.top();
S.pop();
s2=S.top();
S.pop();
op=OP.top();
OP.pop();
output=Reduce(s1,s2,op);
S.push(output);
}
OP.push(str);
}
}
else
{
cout<<"error";
return 0;
}
count++;
}
if(S.size()-OP.size()!=1)
{
cout<<"error";
return 0;
}
while(!OP.empty())
{
string s1,s2,op,output;
s1=S.top();
S.pop();
s2=S.top();
S.pop();
op=OP.top();
OP.pop();
output=Reduce(s1,s2,op);
S.push(output);
}
cout<<S.top();
return 0;
}
发表于 2020-03-28 14:18:46
回复(0)
//遇到and出栈判断，其它情况入栈
public class MeiTuan {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] s = scanner.nextLine().split(" ");
MeiTuan meiTuan = new MeiTuan();
meiTuan.boolString(s);
}
void boolString(String[] bool){
//新建栈用于存放运算符
Stack<String> stack = new Stack<>();
int length = bool.length;
//and和or如果在首尾，出错！
if (bool[0].equals("or")||bool[length-1].equals("or")||bool[0].equals("and")||bool[length-1].equals("and")){
System.out.println("error");
return;
}
for (int i=0;i<length;i++){
String curr=bool[i];
//如果当前为true或false
if (curr.equals("true")||curr.equals("false")){
//如果栈为空，直接压入
if (stack.isEmpty()){
stack.push(curr);
}else {//如果不为空，判断前一个是不是true或false。是，出错；不是的话，如果前一个为or，直接压入；如果为and，相与后再压入
String peek = stack.peek();
if (peek.equals("true")||peek.equals("false")){
System.out.println("error");
return;
}else {
if (peek.equals("or")){
stack.push(curr);
}else {
stack.pop();//取出and
String pre= stack.pop();//取出and的前一个字符串
if (pre.equals("false")||curr.equals("false")){
stack.push("false");
}else {
stack.push("true");
}
}
}
}
}else {
//如果栈顶为or或and
if(stack.isEmpty()){
System.out.println("error");
return;
}else {
String pre1 = stack.peek();
if (pre1.equals("or") || pre1.equals("and")) {
System.out.println("error");
return;
} else {
stack.push(curr);
}
}
}
}
//此时栈中都为true，false，or
while (!stack.isEmpty()){
String end=stack.pop();
if (end.equals("true")){
System.out.println("true");
break;
}
if (stack.isEmpty()){
System.out.println("false");
}
}
}
}
发表于 2020-04-09 11:11:54
回复(0)
一个栈就可以。遇到and就弹出第一个和下一个判断，下一个就不放入栈里了。然后遍历栈 只要有true就输出true（因为这时候只有or了）
import java.util.Scanner;
import java.util.Stack;
public class buerbiaodashi {
public static void Main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
String[] splits = line.split(" ");
if(splits[splits.length-1].equals("and")||splits[splits.length-1].equals("or")) {
System.out.println("error");
return;
}
Stack<String> stack = new Stack<String>();
for(int i=0;i<splits.length;i++) {
String temp = splits[i];
if(i%2==0&&(temp.equals("or")||temp.equals("and"))){
System.out.println("error");
return;
}else if(i%2==1&&(temp.equals("true")||temp.equals("false"))) {
System.out.println("error");
return;
}else {
if(temp.equals("and")) {
temp = stack.pop();
temp = temp.equals("false")||splits[i+1].equals("false")?"false":"true";
stack.push(temp);
i++;
}else {
stack.push(temp);
}
}
}
while(!stack.isEmpty()) {
String istrue = stack.pop();
if(istrue.equals("true")) {
System.out.println("true");
return;
}
}
System.out.println("false");
return;
}
}
发表于 2020-03-18 18:06:36
回复(0)
#include<iostream>
(720)#include<cstdio>
#include<stack>
(850)#include<string>
#include<queue>
(789)#include<map>
using namespace std;
queue<int> q;//后缀队列
stack<int> st;//比较符号栈
map<string,int> mp;//优先级
void check(string s)
{
string t="";
for(int i=0;i<s.size()+1;i++)
{
if(i==s.size()||s[i]==' ')
{
if(t=="true")
q.push(1);
else if(t=="false")
q.push(0);
else
{
if(!st.empty()&&st.top()<mp[t])
{
st.push(mp[t]);
}
else{
while(!st.empty()&&st.top()>=mp[t])
{
q.push(st.top());
st.pop();
}
st.push(mp[t]);
}
}
t="";
}
else{
t+=s[i];
}
}
while(!st.empty())
{
q.push(st.top());
st.pop();
}
}
int cul()
{
stack<int> num;
while(!q.empty())
{
int n=q.front();
if(n==1||n==0)
{
num.push(n);
}
else{
if(num.empty())
return 2;
int c2=num.top();
num.pop();
if(num.empty())
return 2;
int c1=num.top();
num.pop();
if(n==3)
{
if(c1==1||c2==1)
{
num.push(1);
}
else
{
num.push(0);
}
}
else
{
if(c1==1&&c2==1)
{
num.push(1);
}
else
{
num.push(0);
}
}
}
q.pop();
}
if(num.size()>1||num.empty())
{
return 2;
}
else{
return num.top();
}
}
int main()
{
mp["and"]=4;
mp["or"]=3;
string s;
getline(cin,s);
check(s);
int n=cul();
if(n==1)
cout<<"true"<<endl;
else if(n==0)
{
cout<<"false"<<endl;
}
else
{
cout<<"error"<<endl;
}
} 我的思路是本题与简单计算器中中缀表达式转后缀表达式类似，将true false and or 转换为后缀表达式，然后进行计算。
发表于 2020-03-10 19:56:37
回复(1)
#include<iostream>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
int eval(){
int b,a;
if(num.size()!=0)
{ b = num.top();num.pop();}
else{
cout<<"error";
return 0;
}
if(num.size()!=0)
{
a = num.top();num.pop();
}
else{
cout<<"error";
return 0;
}
auto c = op.top();op.pop();
int x ;
if(c == '&') x = a&b;
else x = a|b;
num.push(x);
return 1;
}
int main(){
string str;
int cnt = 1;
//定义优先级
unordered_map<char,int> pr{{'&',1},{'|',0}};
while(cin>>str){
if(cnt%2==1){
//是true false
if(str!="true"&&str!="false"){
cout<<"error";
return 0;
}
if(str=="true") num.push(1);
else num.push(0);
}else{
//是and &nbs***bsp; if(str!="and"&&str!="or"){
cout<<"error";
return 0;
}
char op_pos;
if(str == "and") op_pos = '&';
else op_pos = '|';
while(op.size()&&pr[op.top()]>=pr[op_pos]) if(!eval()) return 0;
op.push(op_pos);
}
cnt++;
}
while(op.size()) if(!eval()) return 0;
if(num.top()==1)cout<<"true";
else cout<<"false";
return 0;
}
发表于 2022-03-04 16:47:55
回复(0)
简简单单两小时，太菜了，害~
使用一个栈，只存“true”、“false”、“or”。
如果第一个字符串是true或false，就入栈，这样后面就不用频繁判断栈空了；否则返回error
循环判断字符串数组
遇到“#” 跳过本次循环
遇到T F
如果栈顶是or，则入栈
否则返回error
遇到or
如果stack不为空 并且栈顶不为or 则入栈；
否则error
遇到and
如果stack为空或者i+1越界或者i+1不是T F，则返回error；
否则弹出一个元素，与下一个元素and运算，将下一个结果标记为“#”。将结果压入栈
到达字符串数组末尾，弹出所有元素并进行or运算，将结果返回import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String[] s = sc.nextLine().split(" ");
sc.close();
String str = helper(s);
System.out.println(str);
}
public static String helper(String[] s){
Deque<String> stack = new LinkedList<>();
String tmp = "";
if (s[0].equals("true") || s[0].equals("false")) {
stack.push(s[0]);
}else {
return "error";
}
for (int i = 1; i < s.length; i++) {
String s1 = s[i];
if(s1.equals("#")){
continue;
}
if (stack.peek().equals("true") || stack.peek().equals("false")) {
if (s1.equals("or") && i + 1 < s.length) {
stack.push(s1);
}else if (s1.equals("and") && i + 1 < s.length) {
tmp = stack.pop();
boolean t1 = Boolean.parseBoolean(tmp) && Boolean.parseBoolean(s[i+1]);
stack.push(String.valueOf(t1));
s[i+1] = "#";
}else {
return "error";
}
}else {
//栈顶是or
if (s1.equals("true") || s1.equals("false")) {
stack.push(s1);
}else {
return "error";
}
}
}
if (!stack.isEmpty() || stack.peek().equals("true") || stack.peek().equals("false")){
tmp = stack.pop();
boolean res = Boolean.parseBoolean(tmp);
while (!stack.isEmpty()){
tmp = stack.pop();
if (!tmp.equals("or")) {
res |= Boolean.parseBoolean(tmp);
}
}
return String.valueOf(res);
}else {
return "error";
}
}
}
发表于 2020-10-10 20:19:49
回复(0)
使用递归下降法来做，代码会比较优雅。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
enum class Token {
True, False, And,&nbs***bsp;
};
vector<Token> tokens;
int idx;
void handleError() {
cout << "error" << endl;
exit(0);
}
bool hasMore() {
return idx < tokens.size();
}
Token peek() {
if (!hasMore()) handleError();
return tokens[idx];
}
Token next() {
if (!hasMore()) handleError();
return tokens[idx++];
}
bool readBool();
bool calcExpr();
bool calcTerm();
bool calcExpr() {
bool res = calcTerm();
while (hasMore()) {
Token token = peek();
if (token != Token::Or) break;
next();
res |= calcTerm();
}
return res;
}
bool calcTerm() {
bool res = readBool();
while (hasMore()) {
Token token = peek();
if (token != Token::And) break;
next();
res &= readBool();
}
return res;
}
bool readBool() {
Token token = next();
if (token != Token::True && token != Token::False) handleError();
return token == Token::True;
}
int main() {
string s;
while (cin >> s) {
if (s == "true") {
tokens.push_back(Token::True);
} else if (s == "false") {
tokens.push_back(Token::False);
} else if (s == "and") {
tokens.push_back(Token::And);
} else if (s ==&nbs***bsp;{
tokens.push_back(Token::Or);
}
}
bool res = calcExpr();
if (hasMore()) {
handleError();
}
if (res) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
发表于 2020-08-19 22:47:37
回复(0)
import java.util.Scanner; import java.util.Stack; public class Main { public static String judgeString(String a){ String result = new String(); if(a == null){ return "error"; } String[] s = a.split(" "); Stack<String> stack =new Stack<String>(); if(isLogical(s)) { if (s.length == 1) { result = s[0]; } else { for (int i = 0; i < s.length; i++) { if (!s[i].equals("and")) { stack.push(s[i]); } else { String temp1 = stack.pop(); //System.out.println(temp1 + "1"); String temp2 = s[i + 1]; //System.out.println(temp2 + "2"); if (temp2.equals("true") && temp1.equals("true")) { stack.push("true"); } else { stack.push("false"); } i = i + 1; } } String temp3 = new String(); String temp = stack.pop(); if (stack.size() == 1) { result = temp; } else{ for (int i = 0; i < stack.size(); i++) { //temp = stack.pop(); temp3 = stack.pop(); //System.out.println(temp3 + "3"); if (temp3.equals("or")) { String temp4 = stack.pop(); //System.out.println(temp4 + "4"); if (temp.equals("false") && temp4.equals("false")) { temp = "false"; } else { temp = "true"; } } } result = temp; } } } else{ result = "error"; } return result; } public static boolean isLogical(String[] s){ int a1 = 0; int a2 = 0; int a3 = 0; int a4 = 0; boolean b = true; if(s.length%2 == 0){ b = false; } for(int i = 0;i < s.length;i++){ if(s[i].equals("true")){ a1++; } if(s[i].equals("false")){ a2++; } if(s[i].equals("or")){ a3++; } if(s[i].equals("and")){ a4++; } } if(a1+a2+a3+a4!=s.length){ b = false; } for(int i = 0;i<s.length - 1;i++){ if(s[i].equals(s[i+1])){ b = false; break; } } if(s[s.length - 1].equals("or")||s[s.length - 1].equals("and")){ b = false; } if(s[0].equals("or")||s[0].equals("and")){ b = false; } return b; } public static void main(String args[]){ Scanner scanner = new Scanner(System.in); String a = scanner.nextLine(); String b = judgeString(a); System.out.println(b); } }
发表于 2020-03-12 08:48:27
回复(0)
写的一些解释，一个Ctrl + Z后退全没了，关键是不能前进。。。不讲了，直接上代码😑
import java.util.*;
public class Main{
public static void main(String[] strs){
String str = cal();
System.out.println(str);
}
public static String cal(){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine().trim();
// String str = "false&nbs***bsp;true and false";
String[] words = str.split(" ");
// System.out.println(Arrays.toString(words));
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < words.length; i++){
if(words[i].equals("true")){
stack.push(1);
}else if(words[i].equals("false")){
stack.push(0);
}else if(words[i].equals("and")){
if(!stack.isEmpty() && stack.peek() != 2 && i != words.length - 1
&& (words[i + 1].equals("true") || words[i + 1].equals("false"))){
int val = words[i + 1].equals("true") ? 1 : 0;
stack.push(stack.pop() & val);
i++;
}else return "error";
}else if(words[i].equals("or")){
stack.push(2);
}else return "error";
}
int last = -1;
while (!stack.isEmpty()){
if(last == -1){
last = stack.pop();
if(last == 2) return "error";
}else{
int or = stack.pop();
if(or != 2) return "error";
int val = 0;
if(!stack.isEmpty() && stack.peek() != 2) val = stack.pop();
else return "error";
last = last | val;
}
}
return last == 1 ? "true" : "false";
}
}
编辑于 2020-03-10 14:31:47
回复(0)
解题思路：
将字符串分割后分别压栈，若遇到顶层为and时候进行弹出对比，最后保证栈中只有true、false、or字符串，再对栈中符号进行判断
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String[] ss=scanner.nextLine().split(" ");
Stack<String> stack=new Stack<>();
for(int i=0;i<ss.length;i++){
String curr=ss[i];
//当前值为true或false时
if(curr.equals("true")||curr.equals("false")){
if(stack.isEmpty()){
stack.push(curr);
}else{
String top=stack.peek();
if(top.equals("true")||top.equals("false")){
System.out.println("error");
return;
}else{
if(top.equals("or")) stack.push(curr);
else{
stack.pop();
String pre=stack.pop();
if(curr.equals("false")||pre.equals("false")) stack.push("false");
else stack.push("true");
}
}
}
}
//当前值为and或or时
else{
if(stack.isEmpty()){
System.out.println("error");
return;
}else{
String top=stack.peek();
if(top.equals("and")||top.equals("or")){
System.out.println("error");
return;
}
stack.push(curr);
}
}
}
if(!stack.isEmpty()&&(stack.peek().equals("or")||stack.peek().equals("and"))){
System.out.println("error");
return;
}
while(!stack.isEmpty()){
String curr=stack.pop();
if(curr.equals("true")){
System.out.println("true");
break;
}
if(stack.isEmpty()) System.out.println("false");
}
}
发表于 2020-03-08 12:12:06
回复(2)
a=input()
try:
print("true"ifeval(a.replace("t","T").replace("f","F")) else"false")
except:
print("error")
发表于 2020-03-11 21:27:52
回复(1)
#include <cstdio>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int main() {
string s;
vector<string>v;
while (cin>>s) { // 注意 while 处理多个 case
v.push_back(s);
char c = getchar();
if(c=='\n'){
break;
}
// stringstream is(s);
// string tmp;
}
//cout<<v.size()<<endl;
stack<string>st_signal;
stack<string>st_bool;
//把所有string归类
bool ret = false;
for (int i = 0; i < v.size(); i++) {
if(i==v.size()-1){
if(v[i]=="and"||v[i]=="or"){
cout<<"error"<<endl;
return 0;
}
}
if (v[i] != "and" && v[i] !=&nbs***bsp;{
st_bool.push(v[i]);
} else {
if (v[i] == "and") {
bool first, second;
if (st_bool.empty()) {
ret = false;
break;
}
if (st_bool.top() == "false") {
first = false;
} else {
first = true;
}
if (i + 1 >= v.size()) {
ret = false;
break;
} else {
if (v[i + 1] == "false") {
second = false;
} else {
second = true;
}
i++;
}
st_bool.pop();
if (first && second == true) {
st_bool.push("true");
} else {
st_bool.push("false");
}
} else {
st_signal.push("or");
}
}
}
if ((st_signal.size() == 0 && st_bool.size() > 1)||(st_signal.size()>st_bool.size())) {
cout << "error" << endl;
return 0;
}
while (!st_signal.empty()) {
if (st_bool.size() <= 1) {
ret = false;
break;
} else {
bool first = st_bool.top() == "true" ? true : false;
st_bool.pop();
bool second = st_bool.top() == "true" ? true : false;
st_bool.pop();
if (first || second) {
st_bool.push("true");
} else {
st_bool.push("false");
}
}
}
if (st_bool.size() == 1) {
cout << st_bool.top() << endl;
} else {
cout << "error" << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld"
硬干就完事了
发表于 2024-03-11 20:35:58
回复(0)
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String[] splits=str.split(" ");
int n=splits.length;
LinkedList<String> stack=new LinkedList<>();
for(int i=0;i<n;i++){
if(splits[i].equals("and")){
if(stack.isEmpty()){
System.out.println("error");
return;
}
String last= stack.removeLast();
if(i+1==n||splits[i+1].equals("and")||splits[i+1].equals("or")){
System.out.println("error");
return;
}
stack.addLast(checkAnd(last,splits[++i]));
}else{
stack.addLast(splits[i]);
}
}
if(stack.size()==1){ // 要么只剩下一个，就是答案，要么至少三个
String last=stack.removeLast();
if(last.equals("and")||last.equals("or")){
System.out.println("error");
return;
}
System.out.println(last);
return;
}
String s1=stack.removeFirst(),ans="";
// 全部剩下or
while(!stack.isEmpty()){
// 至少有两个
if(stack.size()<2){
System.out.println("error");
return;
}
stack.removeFirst(); // 丢弃or符号
String s2=stack.removeFirst();
if(s2.equals("and")||s2.equals("or")){
System.out.println("error");
return;
}
s1=ans=checkOr(s1,s2);
}
System.out.println(ans);
}
static String checkAnd(String s1,String s2){
boolean b1=s1.equals("true")?true:false,b2=s2.equals("true")?true:false;
return b1&&b2?"true":"false";
}
static String checkOr(String s1,String s2){
boolean b1=s1.equals("true")?true:false,b2=s2.equals("true")?true:false;
return b1||b2?"true":"false";
}
}
发表于 2022-08-28 22:32:37
回复(0)
该题采用语法分析解决, 文法规则如下
Or -> And or Or | And And -> T and And | T T -> true | false 文法开始符：Or 非终结符： Or And T 终结符 true false and or
写递归下降算法
记得每遍历到一个终结符, 都需要调用一次getToken函数
// token
enum Token {
// 可以理解为
// private static final Token TRUE = new Token("key")
TRUE("true"), FALSE("false"), END("end"), AND("and"), OR("or");
private final String key;
private Token(String key) {
this.key = key;
}
private String getKey() {
return key;
}
public static Token findByKey(String key) {
if(key == null)
return null;
for (Token token : Token.values()) {
if(token.getKey().equals(key)) {
return token;
}
}
return null;
}
}
public class Main {
private static String[] strs=null;
private static int index = -1;
private static Token token = Token.END;
private static boolean isError = false;
public static void getToken() {
++index;
if(index == strs.length) {
token = Token.END;
return;
}
token = Token.findByKey(strs[index]);
}
public static boolean&nbs***bsp;{
boolean output = And();
while (token == Token.OR) {
getToken();
boolean tmp =&nbs***bsp; output = tmp || output;
}
return output;
}
public static boolean And() {
boolean output;
if(token == Token.TRUE)
output = true;
else if(token == Token.FALSE)
output =false;
// 出错, 因为And的First集合中并只包含true和false
else {
token = Token.FALSE;
isError = true;
return false;
}
getToken();
if (token == Token.AND) {
getToken();
boolean tmp = And();
output = output && tmp;
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
strs = line.split(" ");
getToken();
boolean output = Main.Or();
// 若读完不是END, 则也算出错
if(token != Token.END || isError) {
System.out.print("error");
}
else{
System.out.print(output);
}
}
}
发表于 2022-03-04 22:26:32
回复(0)
用压栈方法更容易处理一些：
public static void main(String[] args){
String input = "true&nbs***bsp;false and false and false and false";
System.out.println(check(input));
}
public static String check(String input){
Stack<String> stringStack = new Stack<>();
String[] words = input.split(" ");
for(int i=0;i< words.length;i++){
if(!"true".equals(words[i]) && !"false".equals(words[i]) && !"or".equals(words[i]) && !"and".equals(words[i])){
return "error";
}
}
for (int i = 0; i < words.length; i++) {
// 如果遇到 and 则计算
if("and".equals(words[i])){
boolean front = Boolean.parseBoolean(words[i+1]);
boolean behind = Boolean.parseBoolean(words[i-1]);
Boolean res = front && behind;
// 将栈顶元素修改为 res
stringStack.pop();
stringStack.push(res.toString());
i = i + 1;
continue;
}
// 将 words 压栈
stringStack.push(words[i]);
}
// stringStack.forEach(System.out::println); // 只剩下&nbs***bsp; AtomicReference<String> result = new AtomicReference<>("false");
stringStack.forEach(word -> {
if ("true".equals(word)){
result.set("true");
}
});
return result.get();
}
发表于 2021-10-09 19:44:34
回复(0)
用栈，先合并所有的and，然后再用第二个栈合并所有的or。操作过程中注意判断非法。
def isInvalid(flag, peek):
# true或者false不能连续出现，and或者or不能连续出现
return ((flag == "true"&nbs***bsp;flag == "false") and (peek == "true"&nbs***bsp;peek == "false"))&nbs***bsp;\
((flag == "and"&nbs***bsp;flag == "and") and (peek == "and"&nbs***bsp;peek == "and"))
def doAnd(x, y):
if x[0]=="t" and y[0]=="t":
return "true"
else:
return "false"
def doOr(x, y):
if x[0]=="t"&nbs***bsp;y[0]=="t":
return "true"
else:
return "false"
def do(flags):
# 不能以and和or结尾和开头
if flags[-1] == "and"&nbs***bsp;flags[-1] ==&nbs***bs***bsp;flags[0] == "and"&nbs***bsp;flags[0] ==&nbs***bsp; print("error")
return
stack = []
# 先处理所有and
for flag in flags:
# print(stack, "<-", flag, end=" = ")
if len(stack)==0:
stack.append(flag)
elif isInvalid(flag, stack[-1]):
print("error")
return
elif (flag == "true"&nbs***bsp;flag=="false") and stack[-1]=="and":
pre1 = stack.pop()
pre2 = stack.pop()
stack.append(doAnd(flag, pre2))
else:
stack.append(flag)
# print(stack)
# print("=========================")
stack2 = []
# 再处理所有or
for flag in stack:
# print(stack2, "<-", flag, end=" = ")
if len(stack2)==0:
stack2.append(flag)
elif isInvalid(flag, stack2[-1]):
print("error")
return
elif (flag == "true"&nbs***bsp;flag=="false") and stack2[-1]=="or":
pre1 = stack2.pop()
pre2 = stack2.pop()
stack2.append(doOr(flag, pre2))
else:
stack2.append(flag)
# print(stack2)
print(stack2[0])
flags = input().split()
do(flags)
发表于 2021-05-09 01:10:04
回复(0)
递归链式求解法：
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int judge(string str) {
int flag, reslut, index = 0;
string tmpstr, copystr = str;
stringstream sstr(str);
sstr >> tmpstr;
if (tmpstr == "true")
flag = 1;
else if (tmpstr == "false")
flag = 0;
else
return -1;
index = tmpstr.size() + 1; //记录子串下标（包括空格）
if (sstr >> tmpstr) {
if (tmpstr == "and" || tmpstr ==&nbs***bsp;{
index += tmpstr.size() + 1;
if (tmpstr == "and" && sstr >> tmpstr) {
copystr = str.substr(index);
reslut = judge(copystr); //copystr作为子串递归传参
if (reslut == -1)
return -1;
else
flag = flag & reslut;
}
else if (tmpstr ==&nbs***bsp;&& sstr >> tmpstr) {
copystr = str.substr(index);
reslut = judge(copystr);
if (reslut == -1)
return -1;
else
flag = flag | reslut;
}
else
return -1;
}
else
return -1;
}
return flag;
}
int main() {
string str;
getline(cin, str);
int flag = judge(str);
switch (flag)
{
case -1:
cout << "error" << endl;
break;
case 0:
cout << "false" << endl;
break;
case 1:
cout << "true" << endl;
break;
}
return 0;
}
发表于 2021-04-13 10:14:13
回复(0)
"""
S = expr&nbs***bsp;expr)
expr = bool (and bool)
"""
class Expression:
def __init__(self, op, left=None, right=None):
self.op = op
self.left = left
self.right = right
def execute(self):
left = self.left.execute()
if self.op ==&nbs***bsp;and left:
return True
if self.op == "and" and not left:
return False
right = self.right.execute()
return right
class Bool:
def __init__(self, bool):
self.bool = bool
def execute(self):
if self.bool == "true":
return True
return False
class Interpreter:
def tokenize(self, s):
return s.split()
def parse(self, tokens):
self.index = 0
self.flag = False
ast = self.parse_or_expression(tokens)
if self.flag:
return None
return ast
def parse_or_expression(self, tokens):
left = self.parse_and_expression(tokens)
if self.flag&nbs***bsp;self.index >= len(tokens): return left
if tokens[self.index] ==&nbs***bsp; self.index += 1
right = self.parse_or_expression(tokens)
return Expression("or", left, right)
self.flag = True
return left
def parse_and_expression(self, tokens):
left = self.parse_bool(tokens)
if self.flag&nbs***bsp;self.index >= len(tokens): return left
if tokens[self.index] ==&nbs***bsp; return left
elif tokens[self.index] == 'and':
self.index += 1
right = self.parse_and_expression(tokens)
return Expression('and', left, right)
self.flag = True
return left
def parse_bool(self, tokens):
if self.index >= len(tokens):
self.flag = True
return None
bool = tokens[self.index]
if bool not in ('true', 'false'):
self.flag = True
self.index += 1
return Bool(bool)
source = input()
interpreter = Interpreter()
tokens = interpreter.tokenize(source)
expr = interpreter.parse(tokens)
if expr:
if expr.execute():
print("true")
else:
print("false")
else:
print("error")
发表于 2021-01-19 14:51:35
回复(0)
用操作数栈和操作符栈来解决
注意操作符的优先顺序，如果栈内操作符是and则先进行计算将结果存入操作数栈后再继续。
import java.util.*;
public class Main{
public static String calcSub(String n1, String n2, String ops){
if(ops.equals("and")){
if(n1.equals("true") && n2.equals("true")){
return "true";
}else{
return "false";
}
}else{
if(n1.equals("false") && n2.equals("false")){
return "false";
}else{
return "true";
}
}
}
public static void calc(Stack<String> op, Stack<String> num){
String n1 = num.pop();
String n2 = num.pop();
String ops = op.pop();
num.push(calcSub(n1, n2, ops));
}
//表达式求值
public static String bds(String a){
Stack<String> num = new Stack<>();
Stack<String> op = new Stack<>();
String[] s = a.split(" ");
int flag = 0; //数
for(int i=0;i<s.length;i++){
if(flag == 0) {
if (!s[i].equals("true") && !s[i].equals("false")) {
return "error";
}else{
num.push(s[i]);
flag = 1;
}
}else{
if (!s[i].equals("and") && !s[i].equals("or")) {
return "error";
}else{
//控制优先级
if(!op.empty() && "and".equals(op.peek())){
calc(op, num);
}
op.push(s[i]);
flag = 0;
}
}
}
//这里为了解决 “true and” 最后是操作符的情况
if(flag == 0){
return "error";
}
while(true){
if(op.empty()){
return num.pop();
}
calc(op, num);
}
}
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
System.out.println(bds(scanner.nextLine()));
}
}
编辑于 2021-01-02 18:07:28
回复(0)
问题信息
通过挑战的用户
-
2023-03-10 22:49:43 -
2023-03-10 22:03:48 -
2022-11-03 19:03:21
-
2022-10-09 16:11:26 -
2022-09-17 14:24:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
