[q]

[Sam90]

Có ai biết thuật toán ký pháp BaLan ko, nếu có thì cho mình với nghe, tốt nhất là có mã nguồn, hay địa chỉ web để có nó cũng được. Thanks.

[hiensmart]

Ký pháp Ba lan là cách đặt các phép tính theo số hết rồi mới đến tóan tử. Có thể dùng stack để giải
Vd:a + b -> a b +

[Sam90]

Cái đó thì tui biết, nhưng mà ngặt nỗi chương trình nguồn của nó như thế nào có ai biết ko, theo bạn nói là viết theo stack nhưng mình nghĩ viết kiểu cây cũng được...còn nghĩ tiếp như thế nào thì mình chịu....hic hic hic...

[hiensmart]

Bạn mua vài cuốn cấu trúc dữ liệu là chắc chắn có, hoặc mua sách đề thi Olympic LHP cũng có ngay đầu, hoặc lên google search với từ khóa in2post hoặc post2in hoặc i2p hoặc p2i

[mqt]

Cái này chỉ nên dùng stack thôi. Không dùng tree đâu.

mqt coi như là Sam90 đã biết cách implement stack. Ở đây, vì mqt không có biết nhiều chữ tiếng Việt trong lĩnh vực vi tính cho nên mqt định nghĩa lại.

Minimum set of functionalities of a stack:
push: bỏ một element vô stack
pop: lấy một element ra khỏi stack (tất nhiên là biết giá trị của nó luôn)
top: xem giá trị của element ở đầu stack. element không có bị lấy ra khỏi stack.
IsEmpty: returns true nếu không có element nào trong stack. Otherwise, returns false.
count: cho biết số element hiện tại trong stack.

Nói về ký pháp Ba Lan, mqt muốn nhắc lại một chút để mình cùng nghĩ giống nhau.
1 + 2 x 3 -> 1 2 3 x +
(1 + 2) x 3 -> 3 2 1 + x
Bạn thấy không, ký pháp Ba Lan làm cho việc tính toán rất dễ hơn nhiều. Bạn không phải lo nghĩ về dấu ngoặc đơn, hay là lúc nào thì tính phép tính nào trước.

mqt không biết bạn dùng ngôn ngữ gì cho nên ở đây mqt để real codes & pseudo codes lộn xộn.



declare một cái stack và instantiate nó. Gọi là s đi.
declare 3 variables loại double. Gọi là a, b, r.
delcare 1 variable loại string để lấy user input. Gọi là i.

define các functions:
bool IsOperator(string input). IsOperator returns true nếu input là +, -, * hoặc /. Còn không thì returns false.
bool IsNumber(char input). IsNumber returns true nếu input là số (20, 1.2, -5,...). Còn không thì returns false.
double ConvertToNumber(string input). ConvertToNumber converts input string thành double và returns số đó.

prompt user for input và đọc input vô c.

if IsOperator(i){
if s.count() <= 2
hiển thị báo lỗi. // tại không đủ operands để làm phép tính
else if i == "/" && s.Top == 0
hiển thị báo lỗi. // chia cho 0.
else {
a = s.pop();
b = s.pop();

// làm phép tính ở đây
switch (c) {
case "+": r = a + b; break;
case "-": r = a - b; break;
case "*": r = a * b; break;
case "/": r = a / b; break;
}

hiển thị r cho người dùng biết;
s.push(r); // bỏ kết quả vô stack lại
}
}
else if IsNumber(i)
s.push (ConvertToNumber (i));
else
hiển thị báo lỗi; // người dùng bỏ input tầm bậy.


bạn có thể loop những statements trên cho tới khi người dùng input "quit" chẳng hạn.

Không được tỉ mỉ cho lắm nhưng hy vọng cũng giúp cho bạn được phần nào.
;)