代码运行可以参考根目录下README.md中的程序调试和main.cpp

题目标题不能直接跳转，需要把项目拉到本地用编译器打开后才能跳转，或者去仓库里找对应路径的代码文件

代码头部添加using namespace std;可以使用string类型变量

代码头部添加#include <stack>可以使用C++内置stack

1.验证回文串

回文是指正读、反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试设计算法判定给定的字符序列是否为回文。（提示：将一半字符入栈）

这里实现的leetcode第125题 翻转字符串判断或者双指针更方便，但毕竟是栈的题，还是按照课本的意思用栈实现

xxxxxxxxxx
30
1
bool isPalindrome(string s) {
2
    // str为实际操作的字符串
3
    string str;
4
    // 去除str中非字母数字的字符
5
    for (char s_char: s)
6
        if (isalnum(s_char))
7
            str += tolower(s_char);
8
    
9
    // n为字符串长度（仅数字字母）
10
    int n = str.length();
11
    stack<char> stk;
12
    int i;
13
    
14
    // 先循环一半，将每个字符放入到栈中
15
    for (i = 0; i < n / 2; i++)
16
        stk.push(str[i]);
17
    // 上一个for循环执行后i在n/2的位置上，比如"abcde"，循环完时i应该指向b
18
    // 如果字符长度是奇数个，需要让指针后移一位，偶数个就不需要，奇数个时n%2=1，偶数个时n%2=0，所以直接让i加上n%2就可以实现指针的移动
19
    for (i += n % 2; i < n; i++) {
20
        // 如果这里栈顶的元素和指针指向的元素相同就把栈顶元素弹出，i向后移动（这一步在for循环中有写）
21
        // 如果不相同那就说明这个不是回文串，就可以直接返回false
22
        if (stk.top() == str[i])
23
            stk.pop();
24
        else
25
            return false;
26
    }
27
    // 不用担心栈在循环的时候会空，因为栈内的元素是n/2向下取整，i从n/2或n/2+1处开始循环，i<n停止，所以最多也就循环n/2次
28
    // 所以如果走到这里就说明每一个前半和后半的字符都一样，字符串是回文串，可以直接返回true
29
    return true;
30
}

2.计算后缀表达式

从键盘上输入一个后缀表达式，试设计算法计算表达式的值。规定：逆波兰表达式长度不超过一行，输入以“$”作为结束，操作数之间用空格分开，操作符只可能有“+” “-” “*” “/”4种。例如：234 34 + 2*$

思路：

逆波兰表达式的计算就是先读到两个被操作数（其中一个数可能是前面计算出来的），然后读到运算符再对两个数进行运算。

所以可以利用栈，每次读到数就放入栈中，读到运算符就从栈中取出两个元素(数字)进行对应的运算

xxxxxxxxxx
30
1
// 因为有除法运算，可能产生浮点数，所以这里用float
2
float evalRPN(vector<string>& tokens){
3
    stack<float> stk;
4
    // 用于从栈中取出两个数
5
    float tmp_a, tmp_b;
6
    // 遍历传进来的数组
7
    for (auto token:tokens) {
8
        // 这里只考虑字符串为数字或者运算符
9
        // 如果不是运算符就一定是数字，数字直接入栈
10
        if(!(token=="+"||token=="-"||token=="*"||token=="/")){
11
            stk.push((float) atoi(token.c_str()));
12
        }else{
13
            // 这里让tmp_a先等于栈顶元素，所以运算的时候tmp_a要放在运算符的后面
14
            // 例：输入 123 45 -
15
            //    这里123会先入栈，45后入栈，所以先给tmp_a赋值的话tmp_a=45
16
            //    所以在下面运算时要用tmp_b - tmp_a
17
            tmp_a = stk.top();
18
            stk.pop();
19
            tmp_b = stk.top();
20
            stk.pop();
21
            // string用switch会报错，所以这里用了多个if来判断
22
            if (token=="+") stk.push(tmp_b + tmp_a);
23
            if (token=="-") stk.push(tmp_b - tmp_a);
24
            if (token=="*") stk.push(tmp_b * tmp_a);
25
            if (token=="/") stk.push(tmp_b / tmp_a);
26
        }
27
    }
28
    // 上边每次读到运算符会把运算后的结果再次放入栈中，所以要返回栈顶元素
29
    return stk.top();
30
}