Một bài tin !

[m2mpro]

2+((3*4+2)*4+23-2)
Bạn hãy lập trình để người sử dụng nhập vào một string dạng như trên sau đó tính ra kết quả và xuất ra màn hình.
Hiện trại thì em đã tính được nếu biểu thức này chỉ có một cặp ngoặc đơn chứ 2 cặp thì bó tay !! Mong mọi người hướng thuật giải !!!

[gianhut]

có phép chia ko?
cái này quy hoạch động cho nó đơn giản bằng cách tách các cái ngoặc ra.
tìm cái mở ngặc "(" cuối cùng và cái đóng ngoặc ")" cuối cùng trong chuỗi, xong rồi tính mỗi ngoặc. chạy từ trái qua, nếu nó là nhân hay chia thì làm, thay thế kế quả vào chuỗi chạy cho đến khi hết dấu nhân chia rồi thì làm tới cộng trừ từ trái qua, xong rồi thay lại kết quả của cái ngoặc.

[m2mpro]

dạng như trên mà bạn, có thể nhập mọi phép tính.

[gianhut]

ThÌ ĐÃ NÓi CÁch GiẢi RỒi. CỘng TrỪ NhÂn Chia GÌ CŨng Đc SẤt

[bete]

Thân gửi m2pro,

Tui nghĩ như vầy:

Giả sử bạn có 1 hàm f:
- input: 1 chuỗi biểu thức KHÔNG CÓ DẤU NGOẶC
- output: giá trị tính được của biểu thức đó

Hàm f sẽ tính được giá trị của các biểu thức có dạng:
a) toán_hạng (ví dụ: "5")
b) toán_hạng_1 toán_tử_1 .... toán_hạng_k toán_tử_k toán_hạng_k_+_1 (ví dụ "2+5*3")

Tui giả sử bạn đã có hàm f trên và bạn đã xử lý được độ ưu tiên của các toán tử (nhân chia trước; cộng trừ sau)

Bây giờ bạn có thể mở rộng hàm f ra để xử lý dấu ngoặc như sau: mỗi khi bạn gặp dấu mở ngoặc thì bạn gọi f đệ quy để lấy giá trị của toán hạng kế; mỗi khi bạn gặp dấu đóng ngoặc thì thoát khỏi f và trả về giá trị đã tính được (nếu gặp dấu đóng ngoặc dư thì báo lỗi)

Với ví dụ của bạn "2+((3*4+2)*4+23-2)" thì đại khái sẽ như sau:

Gọi f: "2+((3*4+2)*4+23-2)"
........
Đã đọc tới "2+"; gặp '('
  Gọi đệ quy f: "(3*4+2)*4+23-2)"
  Đã đọc tới "2+("; gặp '('
    Gọi đệ quy f: "3*4+2)*4+23-2)"
    Đã đọc tới "2+((3*4+2"; gặp ')'
    => trả về 14 (giá trị của "3*4+2")
  Đã đọc tới "2+((3*4+2)" ....
  .....
  Đã đọc tới "2+((3*4+2)*4+23-2"; gặp ')'
  trả về 77 (giá trị của "14*4+23-2")
  .....
trả về 79 (giá trị của "2+77")

Có rất nhiều cách để xử lý chuỗi biểu thức toán (lý thuyết trình biên dịch)
Cách trên chỉ là 1 cách với hy vọng bạn không phải sửa code bạn đang có nhiều quá

(có gì sai sót mong được góp ý; xin cám ơn)

-thân

[m2mpro]

to @bete: Cám ơn anh bete, em đã phần nào hiểu được cách của anh ..
to @gianhut: Em chưa học quy hoạch động, dù sao cũng cám ơn anh/chị nhiều lắm.

[mr_invincible]

cái này quy hoạch động cho nó đơn giản bằng cách tách các cái ngoặc ra.
tìm cái mở ngặc "(" cuối cùng và cái đóng ngoặc ")" cuối cùng trong chuỗi, xong rồi tính mỗi ngoặc. chạy từ trái qua, nếu nó là nhân hay chia thì làm, thay thế kế quả vào chuỗi chạy cho đến khi hết dấu nhân chia rồi thì làm tới cộng trừ từ trái qua, xong rồi thay lại kết quả của cái ngoặc.

Cái này đâu phải quy hoạch động gì đâu nhỉ, cách thông thường mà
To m2mpro: nếu bạn biết sử dụng bộ nhớ động và danh sách liên kết thì có thể áp dụng để tính (tính xong phần nào thì loại phần đó đi và thêm kết quả vào)

[m2mpro]

Program bieu_thuc;
Uses crt;
Type
     mang = array [1..100] of integer;
Var
     a,b,c:mang;
     s:string;
     n,t,j:integer;
{  - - - - - - Nhap string - - - - - - - }
Procedure nhap;
begin
      Write('Nhap vao bieu thuc can tinh : ');
      Readln(s);
 end;
{  - - - - - - Loai bo khoang trang trong string - - - - - - - }
Procedure loaiktrang(var o:string);
var k:integer;
begin
     k:=pos(#32,s);
     While k <> 0 do  delete(s,k,1);
end;
{  - - - - - - Tim vi tri cua ')' - - - - - - - }
Function find(l:integer):integer;
var i:integer;
begin
     For i:=l to length(s) do
     begin
            If s[i] = ')' then find:=i;
     end;
end;
{ - - - - - - Tao mang_ab - - - - - - }
Procedure tao_mangab;
var i,k:integer;
begin
      j:=1;
      t:=1;
      k:=length(s);
      For i:=1 to k do
            If s[i]='(' then
            begin
                   a[j]:=i;
                   j:=j+1;
            end;
            If s[i]=')' then
            begin
                   b[t]:=i;
                   t:=t+1;
             end;
end;
{ - - - - - - Tinh toan voi dau ngoac- - - - - - }
Procedure tinh(l,r:integer);
var i,k,z,y,x,e:integer;w:string;ch:char;
begin
        For i:=l to r do
        begin
               If s[i]='*' then
               begin
                      val(s[i-1],x,e);s[i]:='+';
                      val(s[i+1],y,e);s[i+1]:='0';
                      z:=x*y;
                      str(z,w);
                      s[i-1]:=w[1];
               end;
               If s[i]='/' then
               begin
                      val(s[i-1],x,e);s[i]:='+';
                      val(s[i+1],y,e);s[i+1]:='0';
                      z:=x div y;
                      str(z,w);
                      s[i-1]:=w[1];
               end;
        end;
        For i:=l to r do
        begin
                If s[i]='+' then
               begin
                      val(s[i-1],x,e);s[i]:='+';
                      val(s[i+1],y,e);s[i+1]:='0';
                      z:=x+y;
                      str(z,w);
                      s[i-1]:=w[1];
               end;
                If s[i]='-' then
               begin
                      val(s[i-1],x,e);s[i]:='+';
                      val(s[i+1],y,e);s[i+1]:='0';
                      If i>3 then 
                      begin
                           s[i-2]:='-';
                           str(y,w);
                           s[i-1]:=w[1];
                      end else
                      begin
                          z:=x-y;
                          str(z,w);
                          s[i-1]:=w[1];
                      end;
               end;
        end;
end;
{ - - - - - - Tinh toan voi dau ngoac- - - - - - }
Procedure tinh_ngoac;
var i,m:integer;
begin
       m:=1;
       For i:=t downto 1 do
       begin
             delete(s,a[i],1);
             delete(s,b[i]-1+m,1);
             tinh(a[i]+m,b[i]-m);
             m:=m+1;
       end;
end;
{ - - - - - - Tinh truoc dau ngoac - - - - - - }
Procedure tinh_trngoac;
var i,k:integer;
begin
       k:=length(s);
       If t>1 then
       begin
       tinh_ngoac;
       tinh(1,a[1]);
       tinh(b[t],k);
       end else
       tinh(1,k);
       Writeln;
end;
{ - - - - - - - Tinh tu dau - - - - - - - }
Procedure tinhbieuthuc;
var i,k,x,e,y:integer;
begin
       k:=length(s);
       val(s[1],x,e);
       c[1]:=x;
       For i:=2 to k do
       begin
              If s[i]='+' then
              begin
                     val(s[i+1],y,e);
                     c[1]:=c[1]+y;
              end;
              If s[i]='-' then
              begin
                     val(s[i+1],y,e);
                     c[1]:=c[1]-y;
              end;
       end;
end;
BEGIN
    nhap;
    loaiktrang(s);
    tao_mangab;
    tinh_trngoac;
    tinhbieuthuc;
    Write('Ket qua la ',c[1]);
    Readln;
END.

Đây là bài hoàn chỉnh của em, tính được rồi nhưng ở chỗ là khi tính như thế này 5+5+5 thì nó lấy 5+5 ra 10 thì không lưu lại vào string[1] được, em không biết liệu mình có thể cho string[1] chứ 2 chữ số là '10' được không. Có ai chỉ em với.
Nếu không, mọi người cứ đánh thử vào 5+5+5 là nó sẽ ra 6 vì 5+5 nó chỉ lưu lại trong string có 1 mà không lưu cái số 0. T.T

[gianhut]

to @bete: Cám ơn anh bete, em đã phần nào hiểu được cách của anh ..
to @gianhut: Em chưa học quy hoạch động, dù sao cũng cám ơn anh/chị nhiều lắm.

ý mình cũng giống như ý của bác bete vậy đó. và đó là 1 ứng dụng của quy hoạch động.
gọi là "cưng" cho nó tiện )

Cái này đâu phải quy hoạch động gì đâu nhỉ, cách thông thường mà
To m2mpro: nếu bạn biết sử dụng bộ nhớ động và danh sách liên kết thì có thể áp dụng để tính (tính xong phần nào thì loại phần đó đi và thêm kết quả vào)

thiệt à?

[gianhut]

là sao ta? trong pascal có hàm insert string ko? ko có thì tách ra rồi cộng qua cộng lại :-|