后缀表达式

链接

本题要求计算表达式的值,但这个表达式有所不同,它不包含括号

比如3.5.2.-*7.+@

要求我们先找到第一个运算符号,然后对前两个数字进行相应的运算

我们可以用一个字符串数组来储存相应的数字,然后用一个索引index来控制每个数字

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;//3.5.2.-*7.+@
    vector<string>nums(10000);
    int m=s.size();
    int index=0;
    for(int i=0;i<m-1;i++){
        if(s[i]=='.'){
            index++;
        }
        else if(s[i]=='+'){
            nums[index-2]=to_string(stoi(nums[index-2])+stoi(nums[index-1]));
            index--;
            nums[index].clear();
        }
        else if(s[i]=='-'){
            nums[index-2]=to_string(stoi(nums[index-2])-stoi(nums[index-1]));
            index--;
            nums[index].clear();
        }
        else if(s[i]=='*'){
            nums[index-2]=to_string(stoi(nums[index-2])*stoi(nums[index-1]));
            index--;
            nums[index].clear();
        }
        else if(s[i]=='/'){
            nums[index-2]=to_string(stoi(nums[index-2])/stoi(nums[index-1]));
            index--;
            nums[index].clear();
        }
        else{
            nums[index]+=s[i];
        }
    }
    cout<<nums[0];
}

时间复杂度:O(n²)

空间复杂度:O(n*m) m 是我预分配的大小