公式字符串求值
题目描述
给定一个字符串str，str表示一个公式，公式里可以有整数，加减乘除和左右括号，返回公式的计算结果（注意：题目中所有运算都是整型运算，向下取整,且保证数据合法，不会出现除0等情况）。
输入描述：
输出一行字符串，代表
s
t
r
(
1
≤
l
e
n
g
t
h
s
t
r
≤
1000
)
str(1 \leq length_{str} \leq 1000)
str(1≤lengthstr≤1000)（保证str计算的结果不会出现除零，int溢出等情况）。
输出描述：
输出一个整数，代表表达式的计算结果。
示例1
输入
48*((70-65)-43)+8*1
输出
-1816
示例2
输入
3+1*4
输出
7
题解：
表达式求值，一般是将中缀表达式转为后缀表达式，然后在后缀表达式中，使用两个栈，一个保存操作符，一个保存数字，从前往后进行计算即可。
本题也可以这样做，在将中缀表达式转为后缀表达式过程中，需要注意的是运算符的优先级，其中 “(” 优先级最低，其次是 加减 运算符，优先级最高的是 乘除 运算符。
注意：此题会出现负数，遇到 ‘-’ 运算符需要特判一下。
代码：
#include <cstdio>
#include <cstring>
using namespace std
;
const int N
= 1010;
char s
[N
];
int nums
[N
];
char ops
[N
];
int k1
, k2
;
int grade( char op
) {
if (op
== '(') return 1;
if (op
== '+' || op
== '-') return 2;
if (op
== '*' || op
== '/') return 3;
return 0;
}
void calc( char op
) {
int y
= nums
[ k1
-- ];
int x
= nums
[ k1
-- ];
int z
;
if ( op
== '+') z
= x
+ y
;
else if ( op
== '-' ) z
= x
- y
;
else if ( op
== '*' ) z
= x
* y
;
else z
= x
/ y
;
nums
[ ++k1
] = z
;
}
int solve() {
k1
= k2
= -1;
int top
= 0, val
= 0;
for (int i
= 0; s
[i
]; ++i
) {
if ( s
[i
] >= '0' && s
[i
] <= '9' ) {
val
= val
* 10 + (s
[i
] & 15);
if ( s
[ i
+1 ] >= '0' && s
[ i
+1 ] <= '9' ) continue;
nums
[ ++k1
] = val
;
val
= 0;
}
else if ( s
[i
] == '(' ) ops
[ ++k2
] = s
[i
];
else if ( s
[i
] == ')' ) {
while ( ops
[k2
] != '(' ) calc( ops
[ k2
-- ] );
k2
--;
}
else {
if ( s
[i
] == '-' ) {
if ( i
== 0 || s
[ i
-1 ] == '(' ) {
val
= 0, ++i
;
while ( s
[i
] >= '0' && s
[i
] <= '9' )
val
= val
* 10 + (s
[ i
++ ] & 15);
nums
[ ++k1
] = -val
;
val
= 0, --i
;
continue;
}
}
while ( k2
>= 0 && grade( ops
[k2
] ) >= grade( s
[i
] ) )
calc( ops
[ k2
-- ] );
ops
[ ++k2
] = s
[i
];
}
}
while ( k2
>= 0 ) calc( ops
[ k2
-- ] );
return nums
[0];
}
int main( void )
{
scanf("%s", s
);
printf("%d\n", solve());
return 0;
}
