首页 > 其他分享 >【洛谷 P1449】后缀表达式 题解(栈+分支)

【洛谷 P1449】后缀表达式 题解(栈+分支)

时间:2024-09-05 22:52:04浏览次数:14  
标签:ch 洛谷 int 题解 样例 stk 后缀 P1449 表达式

后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。

如:【洛谷 P1449】后缀表达式 题解(栈+分支)_运算符 对应的后缀表达式为:【洛谷 P1449】后缀表达式 题解(栈+分支)_入栈_02。在该式中,@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 【洛谷 P1449】后缀表达式 题解(栈+分支)_运算符_03,表示后缀表达式。

输出格式

输出一个整数,表示表达式的值。

样例 #1

样例输入 #1

3.5.2.-*7.+@

样例输出 #1

16

提示

数据保证,【洛谷 P1449】后缀表达式 题解(栈+分支)_运算符_04,答案和计算过程中的每一个值的绝对值不超过 【洛谷 P1449】后缀表达式 题解(栈+分支)_后缀表达式_05


思路

从输入中逐个读入字符,对于每个字符进行如下处理:

  • 如果是 +、-、*、/ 中的一个,则从栈中弹出两个数 a 和 b,将其进行相应的运算后将结果 c 压入栈中。
  • 如果是数字,则将其转化为整数 x,用一个变量存储。
  • 如果是 .,说明当前数字已经读取完毕,将其压入栈中,并将 x 清零。
  • 如果是 @,说明输入结束,跳出循环。

最后,输出栈顶元素即可得到结果。


AC代码

#include <iostream>
#include <stack>
#define AUTHOR "HEX9CF"
using namespace std;

char ch;
stack<int> stk;

void getNum(int &a, int &b)
{
    b = stk.top();
    stk.pop();
    a = stk.top();
    stk.pop();
};

int main()
{
    int x = 0;
    while (~(ch = getchar()))
    {
        int a, b, c;
        if ('@' == ch)
        {
            break;
        }
        switch (ch)
        {
        case '+':
            getNum(a, b);
            c = a + b;
            stk.push(c);
            // cout << a << " + " << b << " = " << c << endl;
            break;
        case '-':
            getNum(a, b);
            c = a - b;
            stk.push(c);
            // cout << a << " - " << b << " = " << c << endl;
            break;
        case '*':
            getNum(a, b);
            c = a * b;
            stk.push(c);
            // cout << a << " * " << b << " = " << c << endl;
            break;
        case '/':
            int a, b, c;
            getNum(a, b);
            c = a / b;
            stk.push(c);
            // cout << a << " / " << b << " = " << c << endl;
            break;
        case '.':
            stk.push(x);
            x = 0;
            break;
        default:
            x = x * 10 + ch - '0';
        }
    }
    cout << stk.top() << endl;
    return 0;
}

标签:ch,洛谷,int,题解,样例,stk,后缀,P1449,表达式
From: https://blog.51cto.com/HEX9CF/11930733

相关文章

  • CodeForces 2009G Yunli's Subarray Queries 题解
    云璃!高质量Div.4,吊打某些Div.2Only/Edu/Div.3。本题是下面四道题目的有机结合,优雅且经典。LuoguP4168[Violet]蒲公英|LuoguP1997faebdc的烦恼|LuoguP3203[HNOI2010]弹飞绵羊|LuoguP3246[HNOI2016]序列建议先完成这四题。(必须指出:用蒲公英的分块方......
  • P3688 [ZJOI2017] 树状数组 题解
    P3688[ZJOI2017]树状数组题解记录一下做这道题的心路历程,说明在没有事先知道“九条是求成了后缀和”的情况下如何发现,以及解释一些部分分的做法。sub1,18pts:暴力搜索无脑枚举,复杂度\(\mathcalO(n^m)\)。代码:#include<bits/stdc++.h>#defineintlonglong#defineloop......
  • AT_arc151 题解 & 数组字典序大小比较求方案数
    很好的一题,做的时候没有一点思路,看了题解。看来做过的题目还是太少了,记录一下经验。注意到$1\leN\le2\times10^5$和$1\leM\le10^9$,如此庞大的数据,dp是肯定不行的。当字典序$A<B$时,当且仅当存在$i$,使得$\forallx\in[1,i)$,$A_x=B_x$且$A_i<B_i$。那么我们对于$......
  • 洛谷P1032 [NOIP2002 提高组] 字串变换
    ac代码:#include<bits/stdc++.h>usingnamespacestd;constintN=15;structnode{ stringstr; intstep;};stringa,b;stringorginal[N];stringtranslated[N];intn,ans;map<string,int>ma;stringtrans(conststring&str,inti,i......
  • CF704B Ant Man 题解
    题目传送门前置知识预设性DP解法考虑统计每个数单独的贡献,然后进行预设性DP。设\(f_{i,j}\)表示当前填了\([1,i]\)时有\(j\)个连续段的最小权值,边界为\(f_{0,0}=0\)。对\(i(i\nes,i\nee)\)填入的位置进行分讨。新开一段后面填入的数都比\(i\)大(如果存......
  • 洛谷 P1516 青蛙的约会 题解
    一道简单的数学题~首先分析题意。精简得出:假设跳了\(t\)次,那么青蛙A的坐标是\((x+mt)\modL\),青蛙B的坐标是\((y+nt)\modL\),列出方程:\[x+mt\equivy+nt\pmodL\]由于余数具有可减性,所以把\(y+nt\)移到左边,得出:\[x-y+mt-nt\equiv0\pmodL\]写成人话:\[(x-y+mt-nt)\mod......
  • 9.5 上午 becoder 模拟赛总结 & 题解
    T1文本编辑器说实话,看到题目的第一瞬间,我还以为gm第一道就放了平衡树。一道链表的模板题,当然愿意也可以用平衡树写,不多说了,直接放代码(100pts):#defineN1000005chars[N],t[N];intnow,pre[N],nxt[N];intmain(){scanf("%s%s",s+1,t+1);intn=strlen(s+1);......
  • 【转载】P1399 [NOI2013] 快餐店 题解
    作者%%%%%%NightTide%%%%%%题目大意求一棵基环树的重心。即一个点,使得树上到其距离最长的点到其的距离最短。注意,这个点不一定是一个节点,可以在树上的任意位置。输出树上到其距离最长的点到其的距离。或者说求基环树最短的直径?(大雾解题思路显然,这颗基环树的直径只有两......
  • [USACO13OPEN] Photo G 题解
    前言题目链接:洛谷。题意简述一个长度为\(n\)的序列,有一些位置染了色。现给出\(m\)条限制,第\(i\)条限制为\(l_i\simr_i\)中有且仅有一个位置染色。求出满足这\(m\)中条件,染色位置个数最多为多少。\(n\leq2\times10^5\),\(m\leq10^5\)。题目分析方法\(1\):差......
  • Baby Ehab Plays with Permutations 题解
    前言题目链接:Codeforces;洛谷。题意简述你有一个长度为\(n\)的序列\(p\)满足\(p_i=i\),你可以进行\(x\)次操作,每次操作找到两个不同的\(i,j\)并且交换\(p_i,p_j\),问最终有几个可能的序列。分别求出\(x=1,\ldots,k\)时的答案。\(1\len\le10^9\),\(1\lek\le......