Tyvj1043

题目链接

分析：
这题堪比立方图
实在是需要耐心和细心
我觉得noip之前做一些这样的题可以提高自己的稳定程度

首先要在整个式子外加一个()
数字好处理，直接塞到一个数字
当遇到符号的时候，先判断一下ta与符号栈栈顶元素的优先级关系
如果栈顶是 ( ，就直接入栈
如果出现优先级不增的情况就要计算
如果当前是 ) ,就匹配括号

tip

有可能式子中会出现负数
计算中就当-操作处理
要是最后的答案是负数
就看一下符号栈栈顶是不是 - 号
是的话输出负数就好了

这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

char s[50];
int len,num[50];
int f[50],tf,tn;

int KSM(int a,int b)
{
    int t=1;
    while (b)
    {
        if (b&1)
           t=t*a;
        b>>=1;
        a=a*a;
    }
    return t;
}

int get(char c)
{
    if (c=='(') return 6;
    if (c==')') return 7;
    if (c=='^') return 5;
    if (c=='+') return 1;
    if (c=='-') return 2;
    if (c=='*') return 3;
    if (c=='/') return 4;
}

int js()
{
    if (tn==1&&f[tf]==2)
    {
        tf--;
        num[tn]=-num[tn];
        return 0;
    }
    int a=num[tn--];
    int b=num[tn--];
    int x=f[tf--];
    if (x==5) num[++tn]=KSM(b,a);
    if (x==1) num[++tn]=a+b;
    if (x==2) num[++tn]=b-a;
    if (x==3) num[++tn]=a*b;
    if (x==4) num[++tn]=b/a;
}

int pd(int x)
{
    int y=f[tf];
    if (x==6||x==7) return 0;
    if (x==5&&y==5) return 1;
    if ((x==1||x==2)&&y!=6) return 1;
    if (x==3&&(y==3||y==4||y==5)) return 1;
    if (x==4&&(y==3||y==4||y==5)) return 1;
    return 0;
}

void doit()
{
    int i=0,j;
    tf=tn=0;
    while (i<len)
    {
        int d=0;
        if (s[i]>='0'&&s[i]<='9')
        {
            while (s[i]>='0'&&s[i]<='9'&&i<len)
               d=d*10+s[i]-'0',i++;
            num[++tn]=d;
            continue;
        }
        else
        {
            int r=get(s[i]); 
            while (pd(r)) js();
            if (r==7)
            {
                while (f[tf]!=6) js();
                tf--;
            }
            else f[++tf]=r;
            i++;
        }   
    }
    while (tn!=1) js();   //
}

int main()
{
    scanf("%s",s+1);
    s[0]='(';
    len=strlen(s);
    s[len]=')';
    len++;
    doit();
    printf("%d",num[1]);
    return 0;
}