[已解决]几道C++不会的题目（栈）

Passepartout

1、小明学习信息学知识时发现数学四则运算能结合出形式不同而结果相同的表达式来，比如：

数学表达式（中缀表达式）：(3 + 4) * 5 - 6
波兰表达式（前缀表达式）：- * + 3 4 5 6
逆波兰表达式（后缀表达式）：3 4 + 5 * 6 -
三种表达式的写法不同，求值过程不同，但最终结果却一样。

以波兰表达式为例，求值过程为：

准备一个栈，逆序扫描表达式
遇到数字则入栈
遇到运算符则出栈两个数做运算（先出栈的在左），运算结果再入栈
重复以上过程直到扫描结束
数字可能大于9，除法下取整，试编程实现。

输入输出格式
输入格式：

输入波兰表达式（数字和运算符都以空格隔开）
输出格式：

输出运算结果
输入输出样例
输入样例1：

- * + 3 4 5 6
输出样例1：

29
输入样例2：

+ 10 10
输出样例2：

20
测试点
测试点：5个测试点，每个测试点得20分。

测试限制：每个测试点时间限制1s，内存限制128M。

数据范围：

字符串长度 <= 100


2、
生活中是没有后悔药的，但是写代码可以有。

电脑中很多编辑文本的地方都会实现一个“撤销”功能，当写下了不想写的，或者删掉了不想删的内容后，可以按快捷键“Ctrl + Z”撤销掉上一个操作。

同时，撤销操作也可以反悔，当撤销了不想撤销的内容后，可以按快捷键“Ctrl + Shift + Z”或者“Ctrl + Y”执行“前进”操作，这样被撤销的内容就又回来啦。

现在定义三种操作：

操作1: 写入m个数
操作2: 撤销
操作3: 前进
请自行在编辑器中体验撤销和前进功能，然后编程完成本题。

输入输出格式
输入格式：

第一行输入一个数n， 表示操作数
之后n行，每行若干个数，第一个数为操作类型，若为操作1，第二个数表示要写入的数据量m，之后m个数。
输出格式：

输出n次操作后剩余的内容（空格隔开，行末无空格）
``输入输出样例`
输入样例：

5
1 2 3 4
1 2 1 2
2
2
3
输出样例：

3 4



3、
输入一个字符串，当出现两个相邻的相同字符时就可以将它们消除。消除之后，可能会出现新的相邻相同字符，比如字符串abccb，消除cc，变成abb，再消除bb，变成a。因此需要重复操作，直到再也没有相邻的相同字符为止，输出最终的字符串。

另外，多对相邻相同字符的消除顺序是不会对结果产生影响的。

输入格式：

输入一个字符串，均为小写字符
输出格式：

输出一个字符串，为最终剩下的字符串，如果为空就输出-1
输入样例1；

abccdeed
输出样例1；

ab
输入样例2：

abba
输出样例2：

-1
数据范围：

40%：长度<=1000
100%：长度<=10^6

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-3-3 07:23:22

现在写不了代码，提一下思路
第一题从后往前看，遇到符号把栈顶两数运算，把新的结果放入栈，在这其中，数字处理也是一大难点
第二题不知道数据范围，如果5000以内，开一个2维数组的栈，2就top减一，3就top加一
第三题，依次把字符加入栈相同的top减2即可

跳转到最佳答案楼层

两手空空儿

等大佬出手，学习一下

准备一个栈，逆序扫描表达式
遇到数字则入栈

我感觉这个是难点，对一个字符串，怎么区分哪里是数字，哪里是符号？
先取一个字符，和 + - * /  （ ） 作比较，都对不上就是数字？？
或者有没有更简便的方法？
----------------------------------------------------------
看错了，按题目的要求，这一步是人工完成，编程怎么实现从数学表达式向波兰表达式的转换呢？
这是数据结构的内容么？ 还没学，头大。。。。。。。。

dolly_yos2

头一次处理波兰表达式，试着写了写

#include <cctype>
#include <iostream>
#include <ranges>
#include <stack>
#include <vector>
struct Token{
    enum class Type{
        Operator,
        Value
    }type;
    union Value{
        unsigned char operation;
        unsigned int value;
    }value;
};
std::istream& operator>>(std::istream& in, Token& token){
    decltype(in.peek()) c;
    do{
        c = in.get();
    }while(!isdigit(c) && c != '+' && c != '-' && c != '*' && c != '/' && !in.eof());
    if(in.eof()) return in;
    switch(c){
        case '+':
        case '-':
        case '*':
        case '/':
            token.type = Token::Type::Operator;
            token.value.operation = c;
            return in;
    }
    token.type = Token::Type::Value;
    token.value.value = c - '0';
    while(isdigit(c = in.get())){
        token.value.value = (token.value.value << 3) + (token.value.value << 1) + (c - '0');
    }
    if(!in.eof()) in.unget();
    return in;
}
int main(){
    std::vector<Token> tokens;
    Token temp;
    while(!std::cin.eof()){
        std::cin >> temp;
        tokens.push_back(temp);
    }
    std::stack<unsigned int> stack;
    for(const auto& token: std::ranges::reverse_view(tokens)){
        if(token.type == Token::Type::Value) stack.push(token.value.value);
        else{
            auto lhs = stack.top();
            stack.pop();
            auto rhs = stack.top();
            stack.pop();
            decltype(lhs) result;
            switch(token.value.operation){
                case '+':
                    result = lhs + rhs;
                    break;
                case '-':
                    result = lhs - rhs;
                    break;
                case '*':
                    result = lhs * rhs;
                    break;
                case '/':
                    result = lhs / rhs;
                    break;
            }
            stack.push(result);
        }
    }
    std::cout << stack.top();
    return 0;
}

sfqxx

领鱼币

sfqxx

再领

zhangjinxuan

现在写不了代码，提一下思路
第一题从后往前看，遇到符号把栈顶两数运算，把新的结果放入栈，在这其中，数字处理也是一大难点
第二题不知道数据范围，如果5000以内，开一个2维数组的栈，2就top减一，3就top加一
第三题，依次把字符加入栈相同的top减2即可

kerln888

领鱼币

怀春少年

领鱼币

追梦少年啊

追梦少年啊

领个币

一位朋友

领个鱼币

阿宅Looker

萌新差一个鱼币做课后作业，来蹭蹭，谢谢大佬

额外减小

先占个楼，让我复习复习