首页 > 其他分享 >CSP历年复赛题-P1981 [NOIP2013 普及组] 表达式求值

CSP历年复赛题-P1981 [NOIP2013 普及组] 表达式求值

时间:2024-06-01 22:22:35浏览次数:25  
标签:NOIP2013 P1981 符号 int str 求值 10000 ns os

原题链接:https://www.luogu.com.cn/problem/P1981

题意解读:中缀表达式求值,只有+,*,没有括号,保留后4位。

解题思路:

中缀表达式求值的典型应用,采用两个栈:符号栈、数字栈,对于没有括号的情况,只需要如下步骤:

1、 遍历表达式每一个字符

2、如果遇到数字,则持续提取数字,保存整数到数字栈

3、如果遇到是符号,则与当前符号栈顶符号比较,如果符号栈顶符号优先级大于等于当前符号,则弹出栈顶符号以及两个数字进行运算,结果压回数字栈

4、最后,对符号栈、数字栈中残留的运算进行操作,直到符号栈为空

5、栈顶元素即为结果

注意:每一步运算、最后输出结果都需要对10000取模。

100分代码:

#include <bits/stdc++.h>
using namespace std;

string str;
stack<char> os; //符号栈
stack<long long> ns; //数字栈
unordered_map<char, int> prior = {{'+', 1}, {'*', 2}};

void eval()
{
    int res;
    char op = os.top(); os.pop();
    int a = ns.top(); ns.pop();
    int b = ns.top(); ns.pop();
    if(op == '+') res = (a + b) % 10000;
    if(op == '*') res = (a % 10000) * (b % 10000) % 10000;
    ns.push(res);
}

int main()
{
    cin >> str;
    int num = 0;
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] >= '0' && str[i] <= '9') //遇到数字,提取整数入数字栈
        {
            long long num = 0;
            int j = i;
            while(str[j] >= '0' && str[j] <= '9' && j < str.length())
            {
                num = num * 10 + str[j] - '0';
                j++;
            }
            ns.push(num);
            i = j - 1;
        }
        else //遇到符号,看符号栈顶符号优先级是否大于等于当前符号,是则对前面的符号和数字进行运算
        {
            if(os.size() && prior[os.top()] >= prior[str[i]])
            {
                eval();
            }
            os.push(str[i]);
        }
    }
    while(os.size()) eval();
    cout << ns.top() % 10000; //主要最后也要%10000,因为表达式可能只有一个数超过4位

    return 0;
}

 

标签:NOIP2013,P1981,符号,int,str,求值,10000,ns,os
From: https://www.cnblogs.com/jcwy/p/18226488

相关文章

  • Day 11 | 20. 有效的括号 、1047. 删除字符串中的所有相邻重复项 、150. 逆波兰表达式
    20.有效的括号讲完了栈实现队列,队列实现栈,接下来就是栈的经典应用了。大家先自己思考一下有哪些不匹配的场景,在看视频我讲的都有哪些场景,落实到代码其实就容易很多了。题目链接/文章讲解/视频讲解:https://programmercarl.com/0020.有效的括号.html思考classSolution:......
  • CSP历年复赛题-P1980 [NOIP2013 普及组] 计数问题
    原题链接:https://www.luogu.com.cn/record/160821231题意解读:统计1~n中x的个数。解题思路:枚举每个数,提取每一位,判断是否等于x。100分代码:#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)......
  • springboot aop 通过参数名称来修改 get请求值
    引入aopimplementation'org.springframework.boot:spring-boot-starter-aop'代码实现`packagecom.photo.photoking.interceptor;importorg.aspectj.lang.ProceedingJoinPoint;importorg.aspectj.lang.annotation.Around;importorg.aspectj.lang.annotation.Asp......
  • 行列式求值,从 $n!$ 优化到 $n^3$
    前置知识\(\sum\)为累加符号,\(\prod\)为累乘符号。上三角矩阵指只有对角线及其右上方有数值其余都是\(0\)的矩阵。如果一个矩阵的对角线全部为\(1\)那么这个矩阵为单位矩阵记作\(I\)。对于矩阵\(A_{n,m}\)和矩阵\(B_{m,n}\)满足\(A_{i,j}=B_{j,i}\)记作\(A=B^T......
  • 【算法】栈——逆波兰表达式求值
    题解:逆波兰表达式求值(栈算法)目录1.题目2.题意2.1逆波兰表达式2.2向零截断3.题解4.总结1.题目题目链接:LINK2.题意这个题目种涉及一些概念,应当适当说一下。2.1逆波兰表达式即后缀表达式,是一种数学表达式的表达方式,我们平时数学所用的称为中缀表达式,即:操作数......
  • 代码随想录算法训练营第十一天 | 20.有效的括号 1047.删除字符串中的所有相邻 重复项
    20.有效的括号题目链接文章讲解视频讲解思路:遍历字符串,如果栈不为空,则进行匹配   如果匹配则出栈,否则入栈   如果栈为空,直接入栈   遍历结束后栈为空则说明全部匹配,否则没有全部匹配classSolution{public:boolisValid(strings){stack<cha......
  • 代码随想录算法训练营第第11天 | 20. 有效的括号 、1047. 删除字符串中的所有相邻重
    今天的题主要是关于栈的,比较简单,一次性过20.有效的括号讲完了栈实现队列,队列实现栈,接下来就是栈的经典应用了。大家先自己思考一下有哪些不匹配的场景,在看视频我讲的都有哪些场景,落实到代码其实就容易很多了。题目链接/文章讲解/视频讲解:https://programmercarl.com/0020.......
  • 表达式树求值的空间复用
    回忆一致\(\mathsf{NC}^1\)电路是说一个\(O(\logn)\)深度,可以由对数空间Turing机生成的布尔电路,这个\(O(\logn)\)层的电路暴力展开就是一颗\(n^{O(1)}\)大小的表达式树.反过来,对于任何一颗表达式树,我们也可以用树分治的方法将其对数空间规约到一个\(O(\log......
  • 代码随想录算法训练营第11天 | 栈与队列 20.有效的括号 1047.删除字符串中的所有相邻
    leetcode20.有效的括号题目20.有效的括号给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。解题思路实现代码leetcod......
  • P1969 [NOIP2013 提高组] 积木大赛
    P1969[NOIP2013提高组]积木大赛题目春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦,大厦可以看成由\(n\)块宽度为\(1\)的积木组成,第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前,没有任何积木(可以看成\(n\)块高度为......