分治

表达式计算4

https://ac.nowcoder.com/acm/problem/50999

题目描述:

给出一个表达式,其中运算符仅包含+,-,*,/,^(加 减 乘 整除 乘方)要求求出表达式的最终值

数据可能会出现括号情况,还有可能出现多余括号情况

数据可能会出现负数的情况

思路:

分治

通过运算符将整个表达式一次次分割来计算

根据优先度低的运算符来分割表达式,这样分治到最后进行数与数的计算的时候就算的是优先度最高的,也就是逆过来了

对于同样优先级的符号,我们取最后一个位置来分割

而且对于在括号里面的加减乘除乘方我们不用其来分割,待去气括号后再用其进行分割

所以,我们每次跑(l, r)的时候,用pos1来记录+或-的位置,用pos2来记录*或/的位置,用pos3来记录^的位置

记录好了以后就先判断特殊的情况,也就是pos1=pos2=pos3=-1,此时括号外面没有运算符,就可能出现两种情况,一是出现多余括号,二是正好最外面一层是括号。那我们就讨论一下,当cnt>0且s[l] = ‘(’,就去掉这个左括号,当cnt<0且s[r] = ')'就去掉这个有括号,当cnt = 0,且s[l] = '(',s[r] = ')'就去掉这两个括号,当cnt = 0,s[l] != '(', s[r] != ')',就获得这个数。

如果没有上述特殊情况,就从加减再到乘除再到乘方去分割表达式

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗!
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}
ll qpow(ll a,ll n){ll ans=1,base=a%mod;while(n){if(n&1)ans=(ans*base)%mod;base=(base*base)%mod;n>>=1;}return ans;}
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

string s;

int getnum(int l, int r){
    int num = 0;
    for(int i = l; i <= r; ++i){
        num = num * 10 + s[i] - '0';
    }
    return num;
}

int calc(int l, int r){
    int pos1 = -1, pos2 = -1, pos3 = -1, cnt = 0;
    for(int i = l; i <= r; ++i){
        if(s[i] == '(')++cnt;
        if(s[i] == ')')--cnt;
        if((s[i] == '+' || s[i] == '-') && cnt == 0)pos1 = i;
        else if ((s[i] == '*' || s[i] == '/') && cnt == 0)pos2 = i;
        else if(s[i] == '^' && cnt == 0)pos3 = i;
    }
    if(pos1 == -1 && pos2 == -1 && pos3 == -1){
        if(cnt > 0 && s[l] == '(')return calc(l + 1, r);
        else if(cnt < 0 && s[r] == ')')return calc(l, r - 1);
        else if(cnt == 0){
            if(s[l] == '(' && s[r] == ')')return calc(l + 1, r - 1);
            else return getnum(l, r);
        }
    }
    if(pos1 != -1){
        if(s[pos1] == '+')return calc(l, pos1 - 1) + calc(pos1 + 1, r);
        else return calc(l, pos1 - 1) - calc(pos1 + 1, r);
    }
    if(pos2 != -1){
        if(s[pos2] == '*')return calc(l, pos2 - 1) * calc(pos2 + 1, r);
        else return calc(l, pos2 - 1) / calc(pos2 + 1, r);
    }
    else if(pos3 != -1)return (int)(pow(calc(l, pos3 - 1), calc(pos3 + 1, r)));
    return 0;
}


int main(){
    cin>>s;
    cout<<calc(0, s.size() - 1)<<endl;
    return 0;
}
全部评论

相关推荐

07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务