表达式求值 栈 运算符优先级表

表达式求值 栈 运算符优先级表

表达式的求值

问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来。

　　# 3 * ( 4 + 8 ) / 2 -5 #

　　注：给表达式设置#，标志扫描的开始和结束。

　　提示算法：设两个栈，一个是操作数栈，用来存放操作数，如3、4、8等，另一个是运算符栈，用来存放运算符。

　　首先将标志“#”进运算符栈的栈底。

　　然后依次扫描，按照栈的后进先出原则进行：

　　（1）遇到操作数，进操作数栈；

　　（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较，

　　若若高于栈顶元素则进栈，继续扫描下一符号，

　　否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中……

模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。

附源程序：

program exsj_1;

const

max=100;

var

number:array[0..max] of integer;

symbol:array[1..max] of char;

s,t:string;

i,p,j,code:integer;

procedure push;{算符入栈运算}

begin

inc(p);symbol[p]:=s[i];

end;

procedure pop;{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算}

begin

dec(p);

case symbol[p+1] of

'+':inc(number[p],number[p+1]);

'-':dec(number[p],number[p+1]);

'*':number[p]:=number[p]*number[p+1];

'/':number[p]:=number[p] div number[p+1];

end;

end;

function can:boolean;{判断运算符的优先级别,建立标志函数}

begin

can:=true;

if (s[i] in ['+','-']) and (symbol[p]<>'(') then exit;

if (s[i] in ['*','/']) and (symbol[p] in ['*','/']) then exit;

can:=false;

end;

begin

write('String : '); readln(s); s:='('+s+')'; i:=1; p:=0;

while i<=length(s) do

begin

while s[i]='(' do {左括号处理]

begin

push; inc(i);

end;

j:=i;

repeat {取数入操作数栈}

inc(i);

until (s[i]<'0') or (s[i]>'9');

t:=copy(s,j,i-j); val(t,number[p],code);

repeat

if s[i]=')' then {右括号处理}

begin

while symbol[p]<>'(' do pop;

dec(p); number[p]:=number[p+1];

end

else

begin {根据标志函数值作运算符入栈或出栈运算处理}

while can do pop;

push;

end;

inc(i);

until (i>length(s)) or (s[i-1]<>')');

end;

write('Result=',number[0]);

readln;
end.