中缀表达式、后缀表达式、调度场算法、表达式树
前言
终于抽出时间更新了 QAQ
忘了今年哪场网络赛，有道Call of Accepted，通过人数很多，队友说去看看那个？我说不了不了，虽然我知道是水题，但是那个算法我不会啊！
终究欠的总是要还的 _(:з」∠)_
- 后缀表达式
https://blog.csdn.net/Antineutrino/article/details/6763722
https://liam0205.me/2016/12/14/Shunting-Yard-Algorithm/
https://blog.csdn.net/walkerkalr/article/details/22798365 - 表达式树
https://blog.csdn.net/buaa_shang/article/details/9124075
简单计算器 - HDU - 1237
思路
模板题（而且还没括号 = =||）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
const int N = 200 + 5;
using namespace std;
struct Data{
int data, type;
};
char s[N];
Data suffix_exp[N];
int pp;
int getPriority(char a){
if(a == '*' || a == '/') return 2;
else if(a == '+' || a == '-') return 1;
else return 0;
}
void getSuffixExp(char s[]){
pp = 0;
stack<char> stk;
for(int i = 0; s[i]; ){
if(s[i] == ' '){
i++;
continue;
}
if(isdigit(s[i])){
sscanf(s + i, "%d", &suffix_exp[pp].data);
suffix_exp[pp++].type = 0;
while(isdigit(s[i])) i++;
}else{
while(!stk.empty() && getPriority(stk.top()) >= getPriority(s[i])){
suffix_exp[pp++] = Data{stk.top(), 1};
stk.pop();
}
stk.push(s[i]);
i++;
}
}
while(!stk.empty()){
suffix_exp[pp++] = Data{stk.top(), 1};
stk.pop();
}
}
double solve(){
stack<double> ans;
for(int i = 0; i < pp; i++){
if(suffix_exp[i].type == 0) ans.push(suffix_exp[i].data);
else{
double t2 = ans.top();
ans.pop();
double t1 = ans.top();
ans.pop();
if(suffix_exp[i].data == '+') ans.push(t1 + t2);
else if(suffix_exp[i].data == '-') ans.push(t1 - t2);
else if(suffix_exp[i].data == '*') ans.push(t1 * t2);
else if(suffix_exp[i].data == '/') ans.push(t1 / t2);
}
}
return ans.top();
}
int main(){
while(true){
gets(s);
if(strlen(s) == 1 && s[0] == '0') break;
getSuffixExp(s);
printf("%.2f\n", solve());
}
}
Call of Accepted - ACM-ICPC 2018 沈阳赛区网络预赛
题意
给定表达式求最大值与最小值，其中xdy表示可以取 [x, x * y] 中的数，并且d是右结合的，且运算优先级比 +-* 高
思路
需要对调度场算法进行改造
因为d是右结合的，故遇到栈顶为d时，不能立即将其弹出，而应继续入栈
剩下部分同调度场算法
最后是解决最大值最小值的问题，因为视作区间进行运算，’+’的范围则是小+小，大+大，’-‘的范围是大-小，小-大，’*‘的范围较难确定，但可以确定必然是端点之间乘出来的，所以枚举结果sort一下即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <algorithm>
const int N = 100 + 5;
using namespace std;
typedef long long ll;
struct Data{
ll data;
int type;
};
struct Num{
ll l, r;
};
char s[N];
Data suffix_exp[N];
int pp;
int getPriority(char a){
if(a == 'd') return 3;
else if(a == '*' || a == '/') return 2;
else if(a == '+' || a == '-') return 1;
else return 0;
}
void getSuffixExp(char s[]){
pp = 0;
stack<char> stk;
for(int i = 0; s[i]; ){
if(isdigit(s[i])){
sscanf(s + i, "%lld", &suffix_exp[pp].data);
suffix_exp[pp++].type = 0;
while(isdigit(s[i])) i++;
}else{
if(s[i] == ')'){
while(stk.top() != '('){
suffix_exp[pp++] = Data{stk.top(), 1};
stk.pop();
}
stk.pop();
}else{
while(s[i] != 'd' && s[i] != '(' && !stk.empty() && getPriority(stk.top()) >= getPriority(s[i])){
suffix_exp[pp++] = Data{stk.top(), 1};
stk.pop();
}
stk.push(s[i]);
}
i++;
}
}
while(!stk.empty()){
suffix_exp[pp++] = Data{stk.top(), 1};
stk.pop();
}
}
void solve(ll& ansmin, ll& ansmax){
stack<Num> stk;
for(int i = 0; i < pp; i++){
if(suffix_exp[i].type == 0){
stk.push(Num{suffix_exp[i].data, suffix_exp[i].data});
}else{
Num t2 = stk.top();
stk.pop();
Num t1 = stk.top();
stk.pop();
if(suffix_exp[i].data == '+') stk.push(Num{t1.l + t2.l, t1.r + t2.r});
else if(suffix_exp[i].data == '-') stk.push(Num{t1.l - t2.r, t1.r - t2.l});
else if(suffix_exp[i].data == '*'){
ll choice[4] = {t1.l * t2.l, t1.l * t2.r, t1.r * t2.l, t1.r * t2.r};
sort(choice, choice + 4);
stk.push(Num{choice[0], choice[3]});
}else if(suffix_exp[i].data == 'd'){
stk.push(Num{t1.l, t1.r * t2.r});
}
}
}
ansmin = stk.top().l, ansmax = stk.top().r;
}
int main(){
while(cin >> s){
ll ansmin, ansmax;
getSuffixExp(s);
solve(ansmin, ansmax);
cout << ansmin << " " << ansmax << endl;
}
}
Complicated Expressions - POJ - 1400
题意
对一个表达式，去除其冗余的括号
思路
先将其转为后缀表达式，再建表达式树，最后中序遍历输出
注意输出的时候判定是否需要加括号
① 如果中间的符号比其中一边的优先级大，那么该边需要加括号
② 如果中间的符号与右边的优先级相同，并且中间的符号为’/’或’-‘，那么需要加括号（因为没有结合律）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 250 + 5;
typedef long long ll;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pii;
struct ExpressionTree{
char data;
int ch[2];
};
ExpressionTree tree[N];
pii suffix_exp[N];
char s[N];
int pp;
int getPriority(char ch){
if(ch == '*' || ch == '/') return 2;
else if(ch == '+' || ch == '-') return 1;
else return 0;
}
bool isOperation(char ch){
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')');
}
void getSuffixExp(char s[]){
stack<char> stk;
pp = 0;
for(int i = 0; s[i]; i++){
if(isOperation(s[i])){
if(s[i] == ')'){
while(!stk.empty() && stk.top() != '('){
suffix_exp[pp++] = make_pair(stk.top(), 1);
stk.pop();
}
stk.pop();
}else{
while(s[i] != '(' && !stk.empty() && getPriority(stk.top()) >= getPriority(s[i])){ //)
suffix_exp[pp++] = make_pair(stk.top(), 1);
stk.pop();
}
stk.push(s[i]);
}
}else{
suffix_exp[pp++] = make_pair(s[i], 0);
}
}
while(!stk.empty()){
suffix_exp[pp++] = make_pair(stk.top(), 1);
stk.pop();
}
}
void newNode(int rt, char val){
tree[rt].ch[0] = tree[rt].ch[1] = 0;
tree[rt].data = val;
}
int buildTree(){
int rt = 0;
stack<int> stk;
for(int i = 0; i < pp; i++){
if(suffix_exp[i].second == 0){
newNode(++rt, suffix_exp[i].first);
stk.push(rt);
}else{
int t2 = stk.top();
stk.pop();
int t1 = stk.top();
stk.pop();
newNode(++rt, suffix_exp[i].first);
tree[rt].ch[0] = t1;
tree[rt].ch[1] = t2;
stk.push(rt);
}
}
return rt;
}
void dfs(int u, int pre, bool is_left){
if(!isOperation(tree[u].data)){
putchar(tree[u].data);
return;
}
bool flag = false;
if(pre != -1 && is_left && getPriority(tree[u].data) < getPriority(tree[pre].data)) flag = true;
if(pre != -1 && !is_left){
if(getPriority(tree[u].data) < getPriority(tree[pre].data)) flag = true;
else if(getPriority(tree[u].data) == getPriority(tree[pre].data) && (tree[pre].data == '-' || tree[pre].data == '/')) flag = true;
}
if(flag) putchar('(');
dfs(tree[u].ch[0], u, true);
putchar(tree[u].data);
dfs(tree[u].ch[1], u, false);
if(flag) putchar(')');
}
int main(){
int t;
scanf("%d", &t);
getchar();
while(t--){
gets(s);
getSuffixExp(s);
int rt = buildTree();
dfs(rt, -1, 0);
puts("");
}
}
