栈和队列小练习

Posted by Cww97 on 2018-07-14

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/81043077
这里写图片描述

后缀表达式求值:
遇到数字进栈,遇到符号取两次栈顶元素计算,运算结果扔回栈顶

题目点这

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <map>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 333;

char st[N];

map<char, int> mp; // priority
void init(){
mp['#'] = -1;
mp['('] = 0;
mp['+'] = 1;
mp['-'] = 1;
mp['*'] = 2;
mp['/'] = 2;
mp[')'] = 4; // 单独处理
// 基本符号???
mp['^'] = 3;
}

bool isOperator(char ch){
return ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^';
}
void printVec(vector <char> vec){
for (int i = 0; i < vec.size(); i++){
printf("%c ", vec[i]);
}
puts("");
}
vector<char> getInfix(char* st){
vector <char> infix; // 中缀表达式
stack <char> op;
op.push('#');
for (int i = 0; i < strlen(st); i++){
//printf("st[%d] = %c\n", i, st[i]);
if (isdigit(st[i])){
infix.push_back(st[i]);
} else if (isOperator(st[i])){
if (mp[st[i]] > mp[op.top()]){ // 优先级大于栈顶元素
op.push(st[i]);
}else{ // <=
while (mp[st[i]] <= mp[op.top()]){
infix.push_back(op.top());
op.pop();
}
op.push(st[i]);
}
}else if (st[i] == '('){
op.push(st[i]);
}else { // ')'
while (op.top() != '('){
infix.push_back(op.top());
op.pop();
}
op.pop();
}
}
while (op.top() != '#'){
infix.push_back(op.top());
op.pop();
}
printVec(infix);
return infix;
}

int calc(int x, int y, char op){
if (op == '+') return y + x;
if (op == '-') return y - x;
if (op == '*') return y * x;
if (op == '/') return y / x;
return pow(y, x);
}
// 编译原理
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
init();
scanf("%s", st);
//printf("%s\n", st);
vector <char> infix = getInfix(st);

static int num[N], top;
for (int i = 0; i < infix.size(); i++){
if (isdigit(infix[i])){
num[top++] = infix[i] - '0';
}else { // operator
int &x = num[--top];
int &y = num[--top];
int z = calc(x, y, infix[i]);
//printf("= %dn", z);
num[top++] = z;
for (int j = 0; j < top; j++){
printf("%d ", num[j]);
}
for (int j = i+1; j < infix.size(); j++){
printf("%c%c", infix[j], j+1==infix.size()? '\n': ' ');
}
}
}
//printf("%dn", num[top]);
return 0;
}

luogu2672
推销员

每次找个max,左右判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

int a[N], s[N], n;

int cost(const int &start, int idx){ // index
return (s[idx] - s[start-1])*2 + a[idx];
}

int getMax(const int &start){
int Max = 0, ans = -1;
for (int i = start; i <= n; i++){
if (cost(start, i) > Max){
Max = cost(start, i);
ans = i;
}
}
return ans;
}

int main(){
freopen("in.txt", "r", stdin);
for (; ~scanf("%d", &n);){
for (int i = 1; i <= n; i++){
scanf("%d", &s[i]); // dist
}
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]); // tired
}

int start = 1, ans = 0;
priority_queue <int> Q;
bool flag = 0;
for (int cnt = n; cnt--;){ // count
int x = flag ? start : getMax(start);
if (Q.empty() || Q.top() < cost(start, x)){
ans += cost(start, x);
for (int i = start; i < x; i++) Q.push(a[i]);
start = x + 1;
flag = 0;
}else{
ans += Q.top(); Q.pop();
flag = 1;
}
printf("%d\n", ans);
}
}
return 0;
}