首页 > ACM题库 > HDU-杭电 > hdu 2646 Expression[解题报告]hoj
2014
02-12

hdu 2646 Expression[解题报告]hoj

Expression

问题描述 :

As a shopkeeper of a restaurant,everyday ,dandelion’s mother needs to calculate the incomes.Sometimes,she may make some mistakes.So dandelion wants you to write a program to help her calculate the value of some expressions.
You may consider every expression is made of :left parenthesis ‘(‘ ,right parenthesis ‘)’ , plus sign ‘+’ , subtraction sign ‘-’ , multiplication sign ‘*’ ,positive sign ‘+’ ,and negative sign ‘-’.There is no precursor 0.The length of expression will not exceed 100.The value produced during the calculating will not exceed 10^9.Every expression is legal.Ie. ((10+(-100))) ,-(-1),-3*(+5+7*2)-(0) ,-0 ,(-3)*(-5+7) are legal,while 1+-7 ,–3+8 ,-3+() are illegal.

输入:

There are several cases,every line contains a expression.

输出:

There are several cases,every line contains a expression.

样例输入:

-3*(+5-7*2)-(0)

样例输出:

27

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 210;

int T,cas=1,n,len;
ll ans;
struct Node
{
    int idx, weight;
}a[maxn];
char str[maxn],str2[maxn];
int num[10];

bool operator < (const Node & a, const Node & b)
{
    return (a.weight == b.weight && a.idx > b.idx ) || a.weight > b.weight;
}

void dfs(int &i,int sym)
{
    int cursym=1, cnt=0;
    while (i<len)
    {
        if (str[i]=='#') {cnt++; i++;}
        else
        {
            if (cnt>0)
            {
                for (int j=1,r=1;j<=cnt;j++,r*=10)
                {
                    a[n].idx=i-j;
                    a[n].weight=r*(sym*cursym);
                    n++;
                }
                cnt=0;
            }
            if (str[i]==')') { i++; return; }
            else if (str[i]=='(') { i++; dfs(i,sym*cursym); }
            else if (str[i]=='+') { cursym=1; i++; }
            else if (str[i]=='-') { cursym=-1; i++; }
            else return;
        }
    }
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s%s",str,str2);

        for (int i=0;i<10;i++) num[i]=0;
        for (int i=0;str2[i];i++) num[str2[i]-48]++;

        len=strlen(str);
        str[len]='$'; len++; str[len]=0;
        n=0;
        int i=0;
        dfs(i,1);

        sort(a,a+n);
        ans=0;
        for (int i=0,cur=9;i<n;i++)
        {
            while (num[cur]==0) cur--;
            num[cur]--;
            ans+=cur*a[i].weight;
            str[a[i].idx]=cur+48;
        }

        printf("Case %d:\n",cas++);
        str[--len]=0;
        printf("%s\n",str);
        printf("%lld\n",ans);
    }
	return 0;
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。