giải bài toán hậu tố

[vodanh1222]

Ai pro giải giúp mình bài toán hậu tố này với?
bài toán hậu tố có dạng:
+ 352*+1-=?
+ 30525*+1-=?
có 2 dạng như vậy.
Đầu vào là biểu thức hậu tố, đầu ra là kết quả của biểu thức
(biểu thức hậu tố được chuyển thành từ biểu thức trung tố: 3+5*2-1 và 30+5*25-1)
(Bài giải bằng ngôn ngữ pascal mọi người nha)

[Dustin Đỗ]

Ai pro giải giúp mình bài toán hậu tố này với?
bài toán hậu tố có dạng:
+ 352*+1-=?
+ 30525*+1-=?
có 2 dạng như vậy.
Đầu vào là biểu thức hậu tố, đầu ra là kết quả của biểu thức
(biểu thức hậu tố được chuyển thành từ biểu thức trung tố: 3+5*2-1 và 30+5*25-1)
(Bài giải bằng ngôn ngữ pascal mọi người nha)

***Chuyển trung tố sang hậu tố***



program ConvertInfixToRPN;
uses crt;
const
Opt = ['(', ')', '+', '-', '*', '/'];
var
T, Infix, Stack: string; {Stack dùng chứa toán tử và dấu ngoặc nên dùng String cho tiện}
p: integer;

{Các thao tác với Stack}
procedure StackInit; {Khởi tạo Stack}
begin
stack := '';
end;

procedure Push(V: char); {Thêm phần tử V vào Stack}
begin
stack := stack + V;
end;

function Pop: Char; {Lấy phần tử ra khỏi Stack}
begin
Pop := stack[length(stack)];
dec(stack[0]);
end;

function Get: char;
begin
Get := stack[length(stack)];
end;
{--------------------------------------------------------}
procedure Refine(var S: string); {Hiệu chỉnh biểu thức trung tố về dạng dễ đọc nhất}
var
i: integer;
begin
s:=s + ' ';
for i := length(s) - 1 downto 1 do {Thêm những dấu cách trước và sau nhữg toán tử và dấu ngoặc}
if (s[i] in Opt) or (s[i+1] in Opt) then
Insert(' ', s, i + 1);
for i := length(s) - 1 downto 1 do {Xóa nhữg dấu cách thừa}
if (s[i] = ' ') and (s[i + 1] = ' ') then Delete(s, i+1, 1);
end;

function Priority(Ch: char): integer; {Hàm lấy mức độ ưu tiên của Ch}
begin
case ch of
'*', '/': Priority := 2;
'+', '-': Priority := 1;
'(' : Priority := 0;
end;
end;

procedure Process(T: string); {Xử lý một toán tử đọc đc từ bthức trung tố}
var
c,x: char;
begin
c := t[1];
if not (c in Opt) then Write(T, ' ')
else
case c of
'(': Push(c);
')': Repeat
x := Pop;
if x <> '(' then Write(x, ' ');
Until x = '(';
'+', '-', '*', '/':
begin
while (stack <> '') and (Priority(c) <= Priority(Get)) do
write(Pop, ' ');
Push(c);
end;
end;
end;

begin
Clrscr;
Write('Infix = '); ReadLn(Infix);
Refine(Infix);
WriteLn('Refined: ',Infix);
Write('RPN: ');
T := '';
for p := 1 to Length(Infix) do
if infix[p] <> ' ' then T := T + infix[p]
else
begin
process(t);
T := '';
end;
while Stack <> '' do Write(Pop, ' ');
WriteLn;
ReadLn;
end.


Đã test thành công.
Nhớ tks nha bạn:D

[vodanh1222]

Thanks bác nhiều.bài của bác rất pro.
Nhưng mà bác ơi e muốn nhập in ra kết quả của biểu thức mà? đây là bác mới chuyển trung tố sang hậu tố thôi chứ đã có kết quả của phép toán hậu tố đâu.
đề bài của e là nhập vào biểu thức hậu tố rồi tính kết quả của biểu thức?
Mong bác xem giùm.
Thanks

[Dustin Đỗ]

Thanks bác nhiều.bài của bác rất pro.
Nhưng mà bác ơi e muốn nhập in ra kết quả của biểu thức mà? đây là bác mới chuyển trung tố sang hậu tố thôi chứ đã có kết quả của phép toán hậu tố đâu.
đề bài của e là nhập vào biểu thức hậu tố rồi tính kết quả của biểu thức?
Mong bác xem giùm.
Thanks

bạn thêm phần này (các CTC khác tương tự như trên)


Procedure Calculate(T: String);
var
x,y: Extended;
e: Integer;
begin
if not (T[1] in Opt) then
begin
y := Pop; x := Pop;
case T[1] of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
'/': x := x / y;
end;
Push(x);
end;
end;

begin
write('Enter RPN Expression: ');ReadLn(RPN);
Refine(RPN);
StackInit;
T := '';
for p := 1 to Length(RPN) do {xét các ktự của bthức RPN từ trái qua phải}
if RPN[p] <> ' ' then T := t + RPN[p] {nếu không phải dấu cách thì nối nó vào xâu T}
else {Nếu gặp dấu cách}
begin
Calculate(T); {xử lý phần tử vừa đọc xong}
T := ''; {đặt lại T để cbị đọc ptử mới}
end;
WriteLn(RPN, ' = ', Pop:0:4); {in gtrị bthức đc lưu trog stack}
end.


bạn xem thử, phần này mình chưa test:D

[vodanh1222]

Không được bác ơi.nó báo lỗi ở phần này " y := Pop; x := Pop;".
nếu mà thêm vào thì chắc phải làm lại pop pusd rồi.

[Dustin Đỗ]

Không được bác ơi.nó báo lỗi ở phần này " y := Pop; x := Pop;".
nếu mà thêm vào thì chắc phải làm lại pop pusd rồi.

giờ mình đag bận, để tối nay mình viết code đầy đủ cho bạn...thông cảm nha:D

[vodanh1222]

Bác ơi bác làm chưa vậy.chỉ cần làm phần tính toán biểu thức hậu tố thôi chứ không cân phải chuyển từ trung tố qua đâu.
thanks

[Dustin Đỗ]

{$N+,E+}
program CalculateRPNExpression;
const
Opt = ['+', '-', '*', '/'];
var
T, RPN: String;
Stack: array[1..255] of Extended;
p, Last: Integer;
{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - Các thao tác đối với Stack - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }
procedure StackInit;
begin
Last := 0;
end;
procedure Push(V: Extended);
begin
Inc(Last); Stack[Last] := V;
end;
function Pop: Extended;
begin
Pop := Stack[Last]; Dec(Last);
end;
{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - -}
procedure Refine(var S: String); {Hiệu chỉnh biểu thức RPN về khuôn dạng dễ đọc nhất}
var
i: Integer;
begin
S := S + ' ';
for i := Length(S) - 1 downto 1 do {Thêm những dấu cách giữa toán hạng và toán tử}
if (S[i] in Opt) or (S[i + 1] in Opt) then
Insert(' ', S, i + 1);
for i := Length(S) - 1 downto 1 do {Xoá những dấu cách thừa}
if (S[i] = ' ') and (S[i + 1] = ' ') then Delete(S, i + 1, 1);
end;
procedure Process(T: String); {Xử lý phần tử T đọc được từ biểu thức RPN}
var
x, y: Extended;
e: Integer;
begin
if not (T[1] in Opt) then {T là toán hạng}
begin
Val(T, x, e); Push(x); {Đổi T thành số và đẩy giá trị đó vào Stack}
end
else {T là toán tử}
begin
y := Pop; x := Pop; {Ra hai}
case T[1] of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
'/': x := x / y;
end;
Push(x); {Vào một}
end;
end;
begin
Write('Enter RPN Expression: '); ReadLn(RPN);
Refine(RPN);
StackInit;
T := '';
for p := 1 to Length(RPN) do {Xét các ký tự của biểu thức RPN từ trái qua phải}
if RPN[p] <> ' ' then T := T + RPN[p] {nếu không phải dấu cách thì nối nó vào sau xâu T}
else {Nếu gặp dấu cách}
begin
Process(T); {Xử lý phần tử vừa đọc xong}
T := ''; {Đặt lại T để chuẩn bị đọc phần tử mới}
end;
WriteLn(RPN, ' = ', Pop:0:4); {In giá trị biểu thức RPN được lưu trong Stack}
end.

bạn test nhá..vội wá nên chưa test