表达式求值
以下程序计算包含“+”、“-”、“*”、“(”、“)”和正整数的一个表达式的值。以数组num和数组code作为二个栈。其中栈num
用来存储表达式中的数值以及计算的中间结果,栈code用来存储表达式中的运算符号。最终结果存储在num[1]中,程序输出最终求得的一个整数值num[1]。
程序逐字符扫描表达式:
1、如果是运算数,则直接进运算数栈num。
2、如果是运算符:
2.1如果当前运算符级别低于或相同于位于运算符栈顶的前一个运算符的级别,则:
2.1.1 在运算数栈中出栈两次,得到a,b;
2.1.2运算符栈出栈,得运算符p;
2.1.3 将a和b在运算p下的计算结果入运算数栈;
2.1.4当前运算符继续与位于运算符栈顶的前一个运算符比较;
2.2如果当前运算符级别高于位于运算符栈顶的前一个运算符级别,则当前运算符进栈:
3、左括号最高级。右括号最低级
3.1因此,遇左括号时,左括号入栈;但左括号在栈内时,级别低于任何其它符号!
3.2遇右括号时,一直作运算,直至遇上左括号,则简单地作左括号出栈即可,且此时右括号不进栈;为方便起见,程序会在输入的表达式前后加上一对括号。另外,输入数据保证是正确的。请将程序补充完整。
【样例输入】
12+2*34+(45-5)*(6+7)
【样例输出】
600
Program cz2010_6;
var s:ansistring; n,i,tc,tn:longint; x,y:extended;
num:array[1..1001]of extended;
code:array[1..1001]of char;
function cal(x,y:extended;c:char):extended;//计算x和y在运算c下的值
begin
if c='-' then cal:=x-y
else if c='+' then cal:=x+y
else cal:=x*y;
end;
function prio(x,y:char):boolean;//运算符x比运算y级别高吗?
begin
if x='(' then prio:=false
else if x='*' then prio:=true
else if (x='+')and((y='+')or(y='-'))then prio:=true
else if (x='-')and((y='+')or(y='-'))then prio:=true
else prio:=false;
end;
begin
readln(s);s:='('+s+')';
n:=length(s);
x:=0;tc:=0;tn:=0;
for i:=1 to n do begin
if (s[i]>='0')and(s[i]<='9') then
x:=x*10+ord(s[i])-ord('0')
else begin
if x<>0 then begin
inc(tn);num[tn]:=x; x:=0 ;end;
if s[i]='(' then begin
inc(t) ;code[tc]:=s[i];end
else if s[i]=')' then begin
while code[tc]<>s[i] do begin
dec(tn);
num[tn]:= cal(num[tn],num[tn+1],code[tc]) ;
dec(tc);
end;
dec(tc) ;
end else begin //+,-,*
while prio(code[tc],s[i]) do begin
dec(tn);
num[tn]:= cal(num[tn],num[tn+1],code[tc]) ;
dec(tc);
end;
inc(tc);
code[tc]:=s[i] ;
end;
end;
end;
writeln(num[1]:0:0);
end.