6.2 字符串

以字符串本身带有的含义为背景，考察序列操作的问题常常出现。本节将着重讨论字符串的常见处理问题。

6.2.1 括号序列

括号序列是一连串括号组合而成，可以判断合法性的序列。它是学习栈结构经典的例题。

例题： 蓝桥 算法训练 括号检查

参考代码

#include <bits/stdc++.h>
using namespace std;
stack<char> s;
string str;
int main() {
    cin >> str;
    bool flag = true;    // 记录当前序列是否仍然合法
    for (int i=0; i<str.length(); ++i) {
        char c = str[i];
        if (c == '(') {        // 左括号直接入栈
            s.push(c);
        } else {            // 是右括号的情况
            // 如果有左括号，则弹出一个
            if (!s.empty() && s.top() == '(') {
                s.pop();
            } else {    // 否则是多余右括号，不合法，结束循环
                flag = false;
                break;
            }
        }
    }
    // 检查合法性
    if (s.empty() && flag) cout << "yes" << endl;    // 不能有多余左括号
    else cout << "no" << endl;
    return 0;
}

这一做法的思路是，右括号一定与它左侧一个最近的左括号结合，结合后该左括号不能再与其他右括号结合。所有括号必须全部结合。

代码中，bool flag 用作记录合法性，这是因为 for 循环结束时有两种情况——找到多余右括号、没找到多余右括号。我们必须借助这个变量获知遍历时检查到的合法性，这也是常用的一个手段。

当需要 debug 的时候，可以考虑把 stack<> 替换成 vector<> （前者是功能上简化的 vector），方便打印中间结果。

6.2.2 表达式序列

表达式问题通常是计算输入序列，题目会保证这个序列的合法性。

例题 1：AcWing 3302. 表达式求值 *

计算表达式的通解是使用两个栈，分别存储运算符和数字。详细请参考站内题解。

双栈解法模板

#include <bits/stdc++.h>
using namespace std;
// 定义运算符优先级
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
stack<int> num;
stack<char> op;
void eval() {
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}
int main() {
    string s;
    cin >> s;
    for (int i=0; i<s.size(); ++i) {
        char c = s[i];
        if (isdigit(c)) {
            int x = 0, j = i;
            while (j < s.size() && isdigit(s[j])) {
                x = x * 10 + s[j++] - '0';
            }
            i = j - 1;
            num.push(x);
        } else if (c == '(') {
            op.push(c);
        } else if (c == ')') {
            while (op.top() != '(') eval();
            op.pop();
        } else {
            while (!op.empty() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (!op.empty()) {
        eval();
    }
    cout << num.top() << endl;
    return 0;
}

我们这里提供一种递归思路。递归的定义不仅仅是函数调用自身，还可以是多个函数之间互相调用。具体地，我们把表达式可以拆分成更小的元素——表达式、项、因子；并分别写出对应的处理代码。

请参考：算法答疑—-递归实现表达式求值

参考代码

#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
// 函数声明
int exp();
int term();
int fact();
int exp() {
    int res = term();
    while (1) {
        char op = cin.peek();
        if (op == '+' || op == '-') {
            cin.get();
            int value = term();
            if (op == '+') res += value;
            else res -= value;
        } else {
            break;
        }
    }
    return res;    
}
int term() {
    int res = fact();
    while (1) {
        char op = cin.peek();
        if (op == '*' || op == '/') {
            cin.get();
            int value = fact();
            if (op == '*') res *= value;
            else res /= value;
        } else {
            break;
        }
    }
    return res;
}
int fact() {
    int res = 0;
    char c = cin.peek();
    if (c == '(') {
        cin.get();
        res = exp();
        cin.get();
    } else {
        while (isdigit(c)) {
            res = 10 * res + c - '0';
            cin.get();
            c = cin.peek();
        }  
    }
    return res;
}
int main() {
    cout << exp() << endl;
    return 0;
}
/*
(2+3)*(5+7)+9/3
>>>63
*/

由于三个函数互相调用，我们被迫地回忆起，C++ 语言仍然要求被调函数应该首先声明。（在算法竞赛中很少出现需要专门声明函数的状况）。代码中使用到 cin 的相关技巧，但我们仍然建议一次性读入字符串，并使用下标遍历。

使用递归方法的好处是，能够保持清晰逻辑，拆解问题。我们再通过一道例题演示这一方法。

例题 2：蓝桥 正则问题【第八届】【省赛】

原创题解：【蓝桥杯】试题 历届试题 正则问题

参考代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s;
int i;
int n;        // s.length()
int fact();
int seq();
// exp = fact | fact ...
int exp() {
    int res = fact();
    while (s[i] == '|') {
        ++i;
        res = max(res, fact());
    }
    return res;
}
// fact = seq or (exp)seq ...
int fact() {
    int res = 0;
    while (i < n && (s[i] == '(' || s[i] == 'x')) {
        if (s[i] == '(') {
            ++i;
            res += exp();
            ++i;    // ')'
        } else if (s[i] == 'x') {
            res += seq();
        }
    }
    return res;
}
// xxx
int seq() {
    int res = 0;
    while (s[i] == 'x') {
        ++i;
        ++res;
    }
    return res;
}
int main() {
    cin >> s;
    n = s.size();
    cout << exp() << endl;
    return 0;
}

当然，你也可以尝试另外的思路，只使用单个 dfs() 函数也可以解决问题。最重要的是，你能有逻辑地解出问题。你可以体会两种方法在思路上的差别，以及最终达成的一致。

单一函数递归方法：AcWing 1225. 正则问题

6.2.3 字符串操作

本节说明一些可能会用到的 C++ 语法。

• s.substr(int i, int len)
  获得字符串 s 以下标 开始，长度为 的子串。
• s.find(char ch)

查找字符 ch在字符串 s中第一次出现的下标。

• getline(cin, s)
  该函数允许你读入一整行字符串 s，包括空格。
• stringstream *
  它可以帮你完成类型转换。但它的效率较低，部分 OJ 不支持。