2024年3月7日发(作者：)
2．表达式求值
(/c/pas)
【问题描述】
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
【输入】
输入文件为。
输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为0到231-1之间的整数。输入数据保证这一行只有0~ 9、+、*这12种字符。
【输出】
输出文件名为。
输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。
【输入输出样例1】
1+1*3+4 8
【输入输出样例2】
1+1234567890*1 7891
【输入输出样例3】
1+1000000003*1
4
【输入输出样例说明】
样例1计算的结果为8，直接输出8。
样例2计算的结果为1234567891，输出后4位，即7891。
样例3计算的结果为1000000004，输出后4位，即4。
【数据范围】
对于30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
对于80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
对于100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。
这道题我看了一下，全市一百三十多人中，得一百分的只有三十多人，二十来人得了八九十分，其余的，绝大多数只有一二十分。其实，这题并不难，只是烦些，算法及其实现有很多种。作为两校中唯一一个此题全过的，我希望能与大家分享我的思路与算法。
初看这个题目，第一反应是字符串处理+高精度。我是一个水货，
这两方面非常不熟，当时就懵了。回过神后，再仔细看题，发现表达式内的数据都不超过longint范围，且只要输出后四位，甚至不用高位补“0”，这才发现，此题其实挺简单的。万变不离模拟法，我的算法出炉了。
a
c
1
+
2
*
2
*
2
+
1234
如图所示，设一个长整形数组a存数据，一个字符数组c存符号。符号与数据错开来存。i从1扫描至最后，其间若c[i]=’*’,则令a[i+1]:=a[i-1]*a[i+1], a[i-1]:=0,以解决连乘问题。最后，再次扫描数组a，将已有数据累加、取余，输出结果。以图为例，当i=4时，a[5]:=a[3]*a[5]=4，a[3]:=0，以此类推，得a[7]=8。最后（1+8+1234）mod 10000,输出1243。要注意的是，运算中要随时取余，避免一切可能的数据溢出。
程序：
var st:string;
a:array[1..20000000]of longint;
c:array[1..20000000]of char;//我的数组可能开得有些大
k,j,l,i,x:longint;
n,s:qword;ch:char;
begin
assign(input,'');
reset(input);
assign(output,'');
rewrite(output);
i:=0;s:=0;st:='';
while not eoln do//使用字符串读入
begin
read(ch);
st:=st+ch;
if(ch='*')or(ch='+')or(ch=' ')then
begin
inc(i);
val(copy(st,1,length(st)-1),a[i],x);
inc(i);c[i]:=ch;//错开存放
st:='';
end;
end;
inc(i);
val(st,a[i],x);
l:=i;
for i:=1 to l do
begin
k:=i;
if c[k]='*' then
begin
n:=(a[k-1] mod 10000)*(a[k+1] mod 10000);//随时取余
c[k]:=' ';a[k-1]:=0;a[k+1]:=n;
end;
end;
for i:=1 to l do
s:=(s+a[i]) mod 10000;
writeln(s);
close(input);
close(output);
end.
此程序测试结果如下：
时间复杂度为O（n），通过所有测试点总用时不到0.1s。空间复杂度为O（2n），内存消耗较多可能是数组开太大的缘故。程序较简短，源文件仅有1kB。
这就是我的算法与思路。希望得到大家的改进意见。
发布评论