/**
题目：2017计蒜之道 初赛 第二场 百度的科学计算器（简单）
链接：https://nanti.jisuanke.com/t/15504
题意：给一个合法的表达式，包含加号+、减号-、括号()、数字常量，表达式中没有空格。
输入数据保证数字常量以及计算过程中数值绝对值均不超过 10^12，对于浮点型数值常量，保证小数点后不超过 6位。
思路：暴力模拟；python有函数可以直接调用。
坑点：如果表达式中出现过浮点数，那么输出结果保留6位小数，
否则输出整数，不出现小数。
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e6+5;
const double eps = 1e-12;
char op[1005];
double a[1004];
char s[1004];
int n;
int flag;
int main()
{
while(scanf("%d",&n)==1)
{
scanf("%s",s);
flag = 0;
int az = 0, pz = 0;
int len = strlen(s);
for(int i = 0; i < len; ){
LL in = 0;
LL dt = 0;
LL p = 1;
if(s[i]>='0'&&s[i]<='9'){
while(i<len&&s[i]>='0'&&s[i]<='9'){
in = in*10+(s[i]-'0');
i++;
}
if(s[i]=='.'){
flag = 1;
i++;
while(i<len&&s[i]>='0'&&s[i]<='9'){
dt = dt*10+(s[i]-'0');
i++;
p *= 10;
}
}
double x = in+1.0*dt/p;
a[az++] = x;
}else
{
if(s[i]=='-'){
op[pz++] = '-';
i++;
continue;
}
if(s[i]=='+'){
i++;
op[pz++] = '+';
continue;
}
if(s[i]=='('){
i++;
op[pz++] = '(';
continue;
}
if(s[i]==')'){///左结合。找到左边的符号，以及左边的数，然后模拟计算过去。
int pl = pz-1;
while(op[pl]!='(') pl--;
int temp = pl;// pz = tmep;
int cnt = pz-pl-1;
int tempa = az-cnt-1;
double value = a[az-cnt-1];
for(int j = pl+1, k = az-cnt; j < pz; j++,k++){
if(op[j]=='+'){
value += a[k];
}else value -= a[k];
}
pz = temp;
az = tempa;
a[az++] = value;
i++;
continue;
}
}
}
double value = a[0];///已处理所有括号，只有数和-，+符号。左结合计算。
for(int j = 0, k = 1; j < pz; j++,k++){
if(op[j]=='+'){
value += a[k];
}else value -= a[k];
}
if(flag)///如果出现过浮点数。
printf("%.6lf
",value);
else
printf("%lld
",(LL)value);
}
return 0;
}
表达式树解法：可处理加减乘除都出现的情况。
思路：每次把最后进行的计算符号作为根。递归处理。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e3+5;
const double eps = 1e-12;
int lch[maxn], rch[maxn];
struct node
{
double value;
char op;
}t[maxn];
int nc = 0;
char s[maxn];
int isDouble;
int build_tree(char *s,int x,int y)///[x, y)
{
int c1 = -1, c2 = -1, p = 0;
int u;
int sign = 0;
for(int i = x; i < y; i++){
switch(s[i]){
case '(': p++; sign = 1;break;
case ')': p--; sign = 1;break;
case '+': case '-': if(!p) c1 = i; sign = 1;break;///括号外的最后计算的+，-符号。
case '*': case '/': if(!p) c2 = i; sign = 1;break;///括号外的最后计算的*，/符号。
}
}
if(sign==0){///全是数字或者小数点。说明已经是叶子了。
double in = 0;
LL dt = 0;
LL p = 1;
while(x<y&&s[x]!='.'){
in = in*10 + (s[x]-'0');
x++;
}
if(x<y&&s[x]=='.'){
x++;
isDouble = 1;
while(x<y){
dt = dt*10 + (s[x]-'0');
x++;
p = p*10;
}
}
u = ++nc;
t[u].value = in+1.0*dt/p;
lch[u] = 0;
rch[u] = 0;
return u;
}
if(c1<0) c1 = c2;///没有加减符号.
if(c1<0) return build_tree(s,x+1,y-1); ///没有乘除符号，那么应该是被括号包含，去掉两边的括号。
u = ++nc;
lch[u] = build_tree(s,x,c1);
rch[u] = build_tree(s,c1+1,y);
t[u].op = s[c1];
return u;
}
double dfs(int root)
{
if(lch[root]==0&&rch[root]==0){
return t[root].value;
}
char op = t[root].op;
double lans = dfs(lch[root]), rans = dfs(rch[root]);
switch(op){
case '+': return lans+rans;
case '-': return lans-rans;
case '*': return lans*rans;
case '/': return lans/rans;
}
return -1;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
scanf("%s",s);
nc = 0;
isDouble = 0;
int root = build_tree(s,0,strlen(s));/// root=1
double ans = dfs(root);
if(isDouble) printf("%.6lf
",ans);///出现浮点数，输出6位小数，否则输出整数。
else printf("%lld
",LL(ans));
}
return 0;
}