题解 P1054 【等价表达式】
KaenbyouRin · · 题解
作为一名已经退役的选手，平时闲着没事情做一点题，给脑子上点油
因为已经不参加OI了，所以果断用了c++ 17... 因此代码仅供参考，但是思路是通用的：
若我们要对一个表达式求值，首先要干掉表达式外面包着的多余的括号。
若表达式内不含任何符号，只有数字（或者是一个a），那么我们直接返回数字（或者a^1）。
否则，找到优先级最低的且不被括号包着的运算符。找最右边一个（因为我们的运算符都是左结合的）。
比如说 (a + 1) + (a + 2) * 2 - 5 中就是找到最右边的一个减号。
然后递归地，对该符号左右两边的表达式求值。求完值以后根据这个符号是什么做运算，然后返回。
需要注意的是getline读入换行符的问题以及某些数据可能出现的括号不匹配问题。代码里有注释有提到这些问题的解决方案。
代码比较长，但是可读性很高：
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <iostream>
#include <map>
#include <charconv>
/*
作者: ph3rin
警告：本程序使用了c++17的特性。不过思路是通用的啦= =
定义：
自由运算符指没有被包在括号里的运算符
我们不认为小括号是运算符
*/
int calc_power(int x, int y) {
int ret = 1;
for (int i = 0; i < y; ++i) {
ret *= x;
}
return ret;
}
//存储已经求好值的表达式（按照完全的多项式展开储存）
struct EvaluatedExpr {
private:
//这个map里面存储了已经求完值的表达式的信息
//power[i]表示该表达式中a的i次方的系数
//若不存在就默认为0（map的indexer还是很好用的，不存在的话访问上去就建一个0）
std::map<int, long long> power;
public:
EvaluatedExpr() = default;
//一个工具函数，用来创建仅含有一个a^1的表达式值
static EvaluatedExpr create_a() {
EvaluatedExpr expr;
expr.power[1] = 1;
return expr;
}
EvaluatedExpr(const int val) {
power[0] = val;
}
EvaluatedExpr(EvaluatedExpr&& rhs) noexcept(true) = default;
EvaluatedExpr(const EvaluatedExpr& rhs) = default;
EvaluatedExpr& operator = (EvaluatedExpr&& rhs) = default;
EvaluatedExpr& operator = (const EvaluatedExpr& rhs) = default;
//+-^*运算的定义。不要问我为什么乘法定义的是friend...（我就这么写了，打我啊！）
EvaluatedExpr& operator+= (const EvaluatedExpr& rhs) {
for (auto& pair : rhs.power) {
power[pair.first] += pair.second;
}
return *this;
}
EvaluatedExpr& operator-= (const EvaluatedExpr& rhs) {
for (auto& pair : rhs.power) {
power[pair.first] -= pair.second;
}
return *this;
}
EvaluatedExpr& operator^= (const EvaluatedExpr& rhs) {
EvaluatedExpr expr(1);
int p = rhs.power.at(0);
for (int i = 0; i < p; ++i) {
expr = expr * (*this);
}
/*for (auto& pair : power) {
expr.power[pair.first * p] += calc_power(power[pair.first], p);
}*/
*this = std::move(expr);
return *this;
}
friend EvaluatedExpr operator* (const EvaluatedExpr& lhs, const EvaluatedExpr& rhs);
//用于判断两个多项式是否等价。注意不能只遍历lhs的map，因为可能有lhs没有的次方数但是rhs有
friend bool operator == (EvaluatedExpr& lhs, EvaluatedExpr& rhs);
};
EvaluatedExpr operator* (const EvaluatedExpr& lhs, const EvaluatedExpr& rhs) {
EvaluatedExpr ret;
for (auto& i : lhs.power) {
for (auto& j : rhs.power) {
ret.power[i.first + j.first] += (i.second * j.second);
}
}
return ret;
}
bool operator == (EvaluatedExpr& lhs, EvaluatedExpr& rhs) {
for (auto& pair : lhs.power) {
if (rhs.power[pair.first] != pair.second) return false;
}
for (auto& pair : rhs.power) {
if (lhs.power[pair.first] != pair.second) return false;
}
return true;
}
struct Expr {
//一个储存运算符优先级的hash表。不想写switch了QAQ
static std::unordered_map<char, int> const priority;
//检查一个符号，若它是运算符，返回它的优先级；否则返回-1
static int get_priotity(char op) {
auto it = priority.find(op);
if (it != priority.cend()) {
return it->second;
}
return -1;
}
std::string data;
//par_level[i]储存位于i的运算符外面包了多少层括号
//par_pairs[i]储存了位于i的小括号对应的括号的位置
std::vector<int> par_level, par_pairs;
Expr() = delete;
Expr(std::string expr_str) : par_pairs(expr_str.size(), -1),
par_level(expr_str.size(), -1) {
data.reserve(expr_str.size());
for (char c : expr_str) {
//这里我还是用了白名单
//因为貌似getline会把换行符也弄进来= =RE了一下午
if ((c >= '0' && c <= '9') || (priority.find(c) != priority.end()) || c == '(' || c == ')' || c == 'a') {
data.push_back(c);
}
}
std::stack<int> stk;
int level = 0;
for (int i = 0; i < data.size(); ++i) {
switch (data[i])
{
case '(': {
++level;
stk.push(i);
break;
}
case ')': {
//有坑爹的数据左右括号不匹配。此时无视右括号就可以了
if (stk.empty()) {
break;
}
--level;
int prev_left = stk.top();
stk.pop();
par_pairs[i] = prev_left;
par_pairs[prev_left] = i;
break;
}
default: {
if (get_priotity(data[i]) != -1) {
par_level[i] = level;
}
break;
}
}
}
}
int size() const { return data.size(); }
};
std::unordered_map<char, int> const Expr::priority{ {'+', 0}, {'-', 0}, {'*', 1}, {'^', 2} };
//ExprView表示一个子表达式
struct ExprView {
private:
int par_level_reduce, start, count;
const Expr& expr;
public:
ExprView() = delete;
ExprView(const Expr& expr) : ExprView(expr, 0, expr.size(), 0) {
}
ExprView(const Expr& expr, int start, int size, int reduce) : expr(expr), start(start),
count(size), par_level_reduce(reduce) {
//去掉最外层的括号
while (this->expr.par_pairs[this->start] == this->start + this->count - 1) {
++this->start;
this->count -= 2;
//我们这个区间上所有运算符外面包着的括号层数-1
++par_level_reduce;
}
}
char operator[] (int index) const {
return expr.data[start + index];
}
char at(int index) const {
return this->operator[](index);
}
int par_level(int index) const {
return expr.par_level[start + index];
}
int size() const { return count; }
//检查在index位置的字符是否是一个自由运算符，若是则返回它的优先级；否则返回-1
int get_free_op_priotiy(int index) const {
int p = Expr::get_priotity(at(index));
if (p != -1 && par_level(index) - par_level_reduce == 0) {
return p;
}
return -1;
}
//从右到左寻找优先级最低的自由运算符
//之所以从右到左是因为我们的运算符都是左结合的！（划重点）
int find_free_op() {
int ret = -1, min_p = std::numeric_limits<int>::max();
for (int i = count - 1; i >= 0; --i) {
int p = get_free_op_priotiy(i);
//如果是自由运算符 and 比当前找到的运算符优先级都要小
if (p != -1 && p < min_p) {
ret = i;
min_p = p;
}
}
return ret;
}
EvaluatedExpr evaluate() {
int fp = find_free_op();
//如果是没有自由运算符，说明这是一个a或者数字
if (fp == -1) {
int val = 0;
if (at(0) == 'a') {
return EvaluatedExpr::create_a();
}
else {
//这是c++ 17的新特性
//不用c++ 17的话嘛……会稍微麻烦一点
//本质上就是把字符串某一个区间上的字串转化成整数
std::from_chars(expr.data.data() + start, expr.data.data() + start + count, val);
return EvaluatedExpr(val);
}
}
//这里表示运算符左边和右边的子表达式的起点和长度
int l_start = 0 + start, l_size = fp,
r_start = fp + 1 + start, r_size = count - l_size - 1;
//根据运算符进行运算
switch (at(fp))
{
case '+': {
return ExprView(expr, l_start, l_size, par_level_reduce).evaluate()
+= ExprView(expr, r_start, r_size, par_level_reduce).evaluate();
}
case '-': {
return ExprView(expr, l_start, l_size, par_level_reduce).evaluate()
-= ExprView(expr, r_start, r_size, par_level_reduce).evaluate();
}
case '*': {
return ExprView(expr, l_start, l_size, par_level_reduce).evaluate()
* ExprView(expr, r_start, r_size, par_level_reduce).evaluate();
}
case '^': {
return ExprView(expr, l_start, l_size, par_level_reduce).evaluate()
^= ExprView(expr, r_start, r_size, par_level_reduce).evaluate();
}
default:
throw std::runtime_error("Error!");
}
}
};
int main() {
std::string expr_str;
std::string ans;
std::getline(std::cin, expr_str);
Expr expr(expr_str);
EvaluatedExpr&& question_ans = ExprView(expr, 0, expr.size(), 0).evaluate();
ans.reserve(26);
int choice_count;
std::cin >> choice_count;
std::string choice;
//读入开头多余的换行
std::getline(std::cin, choice);
for (int i = 0; i < choice_count; ++i) {
std::getline(std::cin, choice);
Expr o_expr(choice);
EvaluatedExpr&& option_ans = ExprView(o_expr, 0, o_expr.size(), 0).evaluate();
if (question_ans == option_ans) {
ans.push_back('A' + i);
}
}
std::cout << ans << std::endl;
return 0;
}