如何判断一个算数表达式正确与否?(300分)

M

mslf

Unregistered / Unconfirmed
GUEST, unregistred user!
如何判断一个算数表达式正确与否?条件如下: 变量的第一个字符为必须是 A-G 的字符,
再跟着是 1-100 的数字,如不符合该条件或是算式写错,则能判断为错误。如:
( A12 + F44 ) * D56
 
哥们,有时间看看编译原理,比这看大家讲明白的多的多,有些基础知识不如自己看的,呵呵
 
是不是可以把它当作一个字符串 然后逐一拆着判断呢?
 
看看编译原理的移进/归约
 
function IsValidExpression(ExprStr:String):Boolean;
const
Alpha_Number=['0'..'9','A'..'Z','a'..'z','_'];
var
i,n:Integer;
ch:Char;
Str:String;
begin
Result:=true;
i:=1;
while i<=Length(ExprStr)do
begin
ch:=ExprStr;
if ch in ['a'..'z','A'..'Z','_'] then
begin
if ch in ['a'..'g','A'..'G'] then
begin
Str:='';
Inc(i);
while i<=Length(ExprStr)do
begin
ch:=ExprStr;
if ch in Alpha_Number then
begin
Str:=Str+ch;
end
else
//变量名结束
break;
Inc(i);
end;
n:=StrToIntDef(Str,-1);
if (n<1) or (n>100) then
begin
Result:=false;
exit;
end;
end
else
begin
//变量名不是以 a..g 开头
Result:=false;
exit;
end;
end;
Inc(i);
end;
end;
 
用自动机,你能画出状态转换图,编程就容易了。
 
creation-zy, 以下表达式判断错误:(a1+d9
 
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
s: string;
function IsVar(s: string): Boolean;
var
l, i: Integer;
begin
Result:=True;
l:=Length(s);
if l<2 then
begin
Result:=False;
Exit
end;
if not (s[1] in ['A'..'G']) then
begin
Result:=False;
Exit
end;
for i:=2 to ldo
if not (s in ['0'..'9']) then
begin
Result:=False;
Exit
end
end;

function FindOp(s: string): Integer;
var
Count: Integer;
i: Integer;
l: Integer;
begin
l:=Length(s);
i:=0;
Count:=0;
repeat
Inc(i);
if s='(' then
Inc(Count)
else
if s=')' then
Dec(Count)
until ((Count=0) and (s in ['+', '-', '*', '/'])) or (i>l);
if i>l then
Result:=0
else
Result:=i
end;

function Hahaha(s: string): Boolean;
var
p, l: Integer;
s1, s2: string;
begin
l:=Length(s);
if (s[1]='(') and (s[l]=')') then
begin
s1:=Copy(s, 2, l-2);
Result:=Hahaha(s1)
end
else
begin
p:=FindOp(s);
if p=0 then
Result:=IsVar(s)
else
begin
s1:=Copy(s, 1, p-1);
s2:=Copy(s, p+1, l-p);
Result:=Hahaha(s1) and Hahaha(s2)
end
end
end;

begin
Write('Input s: ');
ReadLn(s);
while s<>''do
begin
if Hahaha(UpperCase(s)) then
WriteLn('1')
else
WriteLn('0');
Write('Input s: ');
ReadLn(s)
end
end.
 
为了节约空间,我将有Bug的版本删除,请参考最新版的算法。
 
to creation-zy:
(a3+b3)/c3
 
不用看编译原理
把堆栈看看就行,和出栈,进栈很有关系
 
呵呵,老人家说的对.
此题有三种经典做法,类似于表达式求值 .
1.用两个栈,一个放运算符,一个放变量,运用运算符的优先级进行出入栈,最后根据变量栈和
运算符栈的状态判断合法性.
2.根据表达式构造二叉树,根据构造好的树判断合法性.
3.用再下用的笨办法,如果表达式中没有运算符,则判断表达式是否是合法变量,
如果有运算符,则分别判断运算符前后的表达式是否合法.
 
to LeeChange:
请比较我们的函数:
a3+b4
(a12-5)/(b7+9)
(a12-c5)/e3
d4+-b9
(a7-)+f9
5-(a6-c5))-b6*(1
 
to creation-zy:
呵呵,火眼金星,我忘了判断空串,谢谢.
function Hahaha(s: string): Boolean;
var
p, l: Integer;
s1, s2: string;
begin
l:=Length(s);
if l=0 then
Result:=False
else
if (s[1]='(') and (s[l]=')') then
begin
s1:=Copy(s, 2, l-2);
Result:=Hahaha(s1)
end
else
begin
p:=FindOp(s);
if p=0 then
Result:=IsVar(s)
else
begin
s1:=Copy(s, 1, p-1);
s2:=Copy(s, p+1, l-p);
Result:=Hahaha(s1) and Hahaha(s2)
end
end
end;
 
to creation-zy:
呵呵,个人认为(a12-c5)/e3是正确的表达式
 
5-(a6-c5)-b6*1
a2233
98213

我的函数判断全部正确,请放心.


请使用我在 来自:creation-zy, 时间:2003-4-9 19:00:00, ID:1753414 中的函数 Please.
 
to creation-zy:
5-(a6-c5)-b6*1你我的算法都说他是非法表达式,看来他确实是错了.呵呵.
 
to creation-zy:
呵呵,可我还是觉得(a12-c5)/e3是合法表达式.
 
to LeeChange
你的代码用了递归,最好不用
否则出栈,进栈的意义不大了。
你认为是这样吗?
 
to creation-zy:
呵呵,我明白了.
 
顶部