表达式求值

//遇到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");
            }
        }
    }
}

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;
		}
			
	}

#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;
    }
}

#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;
}

简简单单两小时，太菜了，害~

使用一个栈，只存“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";
        }
    }
}

 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);

    }
}

#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"

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";
    }
}

该题采用语法分析解决, 文法规则如下

 Or -> And or Or | And   And -> T and And | T   T -> true | false
 文法开始符：Or
 非终结符： Or And T
 终结符 true false and or

写递归下降算法

// 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);
        }
    }
}

"""
    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")