2014
02-12

# 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树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。