思路：
这道题与之前的表达式求值题目不同的是，有not这个单目运算符。而且如果表达式错误，要输入error。
把true和false成为操作数，把and or not成为运算符。
考虑error的情况：
1.and 和 or是双目运算符，所以表达式开头和结尾不可以是and 或者 or。
2.not和后面跟着的操作数可以看成一个操作数，所以and 或者 or后面可以跟 not，但not后面不可以跟 and或者 or。
3.操作数和运算符必须是一一间隔的（not和后面的操作数看成操作数），两个操作数不可以挨在一起，两个运算符也不可以挨在一起。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 267; string s[N]; int cnt; bool is_op(string c) { return c == "and" || c == "or" || c == "not"; } int priority(string c) { // 优先级 if (c == "not") return 3; if (c == "and") return 2; if (c == "or") return 1; return -1; } void process_op(stack<string> &st, string op) { // 处理单次运算 string l, r; r = st.top(); st.pop(); if (!st.empty()) { l = st.top(); } if (op == "and") { st.pop(); if (l == "true" && r == "true") st.push("true"); else st.push("false"); } if (op == "or") { st.pop(); if (l == "true" || r == "true") st.push("true"); else st.push("false"); } if (op == "not") { // 单目运算符，不用pop if (r == "true") st.push("false"); else st.push("true"); } } string evaluate(string *s, int cnt) { stack<string> st; // true false栈 stack<string> op; // and or not栈 for (int i = 0; i < cnt; i++) { if ((is_op(s[i]))) { // and or not string cur_op = s[i]; if (cur_op != "not") { // 入栈and or while (!op.empty() && priority(op.top()) >= priority(cur_op)) { // 运算符栈是否为空，并判断优先级 process_op(st, op.top()); // 如果栈顶优先级>=当前优先级，则把栈顶的计算完 op.pop(); } } op.push(cur_op); } else { st.push(s[i]); while (!op.empty() && op.top() == "not") // not { process_op(st, op.top()); op.pop(); } } } while (!op.empty()) { process_op(st, op.top()); op.pop(); } return st.top(); } bool check(string *s, int cnt) // 判断是否error { int s2[N] = {0}; if (s[0] == "or" || s[0] == "and" || s[cnt - 1] == "or" || s[cnt - 1] == "and" || s[cnt - 1] == "not") // 双目运算符在开头或结尾，单目运算符在结尾 return false; for (int i = 0; i < cnt; i++) { if (s[i] == "not" && (s[i + 1] == "or" || s[i + 1] == "and")) // not后面为and 或 or { return false; } } int cnt2 = 0; for (int i = 0; i < cnt; i++) { // 把not忽略后，不能连续两个为操作数true false或连续两个为运算符and or // 1代表操作数，0代表运算符 if (s[i] == "or" || s[i] == "and") { s2[cnt2++] = 1; } else if (s[i] == "true" || s[i] == "false") { s2[cnt2++] = 0; } if (cnt2 >= 2 && (s2[cnt2 - 2] ^ 1) != s2[cnt2 - 1]) { // 判断有无连续的两个0或连续两个1 return false; } } return true; } int main() { while (cin >> s[cnt]) { cnt++; } if (!check(s, cnt)) { cout << "error"; return 0; } cout << evaluate(s, cnt) << endl; return 0; }
