分类目录归档:

Openjudge BJUTACM 1036:括号画家

智障的一开始竟然想用递归/记忆化做。。。老T。后来猛然醒悟是栈。。。

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
void E() {
    cout << "No";
    exit(0);
}
void S() {
    cout << "Yes";
    exit(0);
}
stack<char> s;
int main() {
    char c;
    while (cin >> c) {
        switch (c) {
        case '(':case '[':case '{':
            s.push(c);
            break;
        case ')':case ']':case '}':
            if (s.empty())E();
            switch (c) {
            case ')':
                if (s.top() == '(')s.pop();
                else E();
                break;
            case ']':
                if (s.top() == '[')s.pop();
                else E();
                break;
            case '}':
                if (s.top() == '{')s.pop();
                else E();
                break;
            }
        }
    }
    S();
}

http://bjutacm.openjudge.cn/lianxi/1036/

Openjudge BJUTACM 1018:简单计算器

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int t;
stack<double> si;
stack<char> sc;
inline bool execute() {
    if (sc.empty()) return false;
    double x2 = si.top();
    si.pop();
    double x1 = si.top();
    si.pop();
    char symbol = sc.top();
    sc.pop();
    switch (symbol) {
    case '+':si.push(x1 + x2); break;
    case '-':si.push(x1 - x2); break;
    case '*':si.push(x1 * x2); break;
    case '/':si.push(x1 / x2); break;
    }
    return true;
}
int main() {
    scanf("%d", &t);
    do {
        char c = getc(stdin);
        if (c == -1)break;
        if (c == '\n') {
            while (execute());
            if (si.empty())continue;
            double v = si.top();
            while (!si.empty())si.pop();
            while (!sc.empty())sc.pop();
            printf("%.2lf\n", v);
            continue;
        }
        if (c <= '9' && c >= '0') {
            ungetc(c, stdin);
            double v;
            scanf("%lf", &v);
            if (sc.empty())si.push(v);
            else if (sc.top() == '-') {
                si.push(-v);
                sc.pop();
                sc.push('+');
            }
            else if (sc.top() == '/') {
                si.push(1.0 / v);
                sc.pop();
                sc.push('*');
            }
            else si.push(v);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!sc.empty() && (c == '+' || c == '-') && (sc.top() == '*' || sc.top() == '/')) {
                execute();
            }
            sc.push(c);
        }
    } while (1);
}

http://bjutacm.openjudge.cn/lianxi/1018/

Openjudge扩号匹配问题

2705:扩号匹配问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用”$”标注,不能匹配的右括号用”?”标注.
输入
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100
注意:cin.getline(str,100)最多只能输入99个字符!
输出
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由”$”,”?”和空格组成,”$”和”?”表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x)
)(rttyy())sss)(
样例输出
((ABCD(x)
$$
)(rttyy())sss)(
? ?$

用递归不会做,只能用栈做。
继续阅读