Thắc mắc viết code C tính giá trị một biểu thức

[Nguyen1204 (LeNguyen)]

Dạ mọi người cho e hỏi

Nếu mình tính giá trị của một biểu thức bất kì thì mình viết sao ạ( nếu không dùng stack). Vd với ((12+3*4)/4),ý tưởng bên em là sẽ duyệt từ phải sang trái, về dấu ngoặc thì đã xử lí được nhưng còn biểu thức e không biết phải viết sao để ưu tiên nhân chia trước cộng trừ sao ạ.

Em cảm ơn.

[Stanley00 (Stanley)]

Tại sao lại có yêu cầu không được dùng stack? Bởi vì, nếu dùng stack, thì đã có thuật toán đơn giản hơn là "chuyển biểu thức infix kia về dạng post fix (lúc này sẽ không còn dấu ngoặc và đã có cả thứ tự ưu tiên), rồi dùng stack để tính biểu thức post fix kia là xong

Còn nếu không dùng stack, thì có thể dùng đệ quy để parse (Recursive Descent Parser). Để làm được thì cần định nghĩa “biểu thức” là gì dưới dạng BNF:

<expression> ::= <term> { ('+' | '-') <term> }
<term>       ::= <factor> { ('*' | '/') <factor> }
<factor>     ::= '(' <expression> ')' | <number>
<number>     ::= <digit> { <digit> } [ '.' <digit> { <digit> } ]
<digit>      ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Với:

• <expression> : Mô tả biểu thức: nó bao gồm một Term và có thể có một hoặc nhiều cặp toán tử + hoặc - với các Term khác.
• <term> : Mô tả một phần của biểu thức mà không có toán tử + hoặc - . Nó bao gồm một Factor và có thể có một hoặc nhiều cặp toán tử * hoặc / với các Factor khác. Việc tách Term này nhằm thể hiện phép toán * và / có ưu tiên cao hơn.
• <factor> : Mô tả các phần đơn lẻ của biểu thức, bao gồm số hoặc biểu thức trong ngoặc.
• <number> : Mô tả một số thực. Nó bao gồm một hoặc nhiều chữ số và có thể có một dấu chấm thập phân sau đó là một hoặc nhiều chữ số khác.
• <digit> : Mô tả một chữ số từ 0 đến 9 .

Từ cái này, chỉ cần viết các hàm để parse từng phần như trên:

double parseExpression(const std::string& str, size_t& index);
double parseTerm(const std::string& str, size_t& index);
double parseFactor(const std::string& str, size_t& index);
// Hàm parseNumber thì có thể sử dụng stod

double evaluateExpression(const std::string& str) {
    size_t index = 0;
    return parseExpression(str, index);
}

int main() {
    std::string expression = "((12+3*4)/4)";
    double result = evaluateExpression(expression);
    std::cout << "Result: " << result <<'\n';
    return 0;
}

Ví dụ parse biểu thức ((12+3*4)/4):

<expression>
  |
  +-- <term>
  |     |
  |     +-- <factor>
  |     |     |
  |     |     +-- '('
  |     |     |
  |     |     +-- <expression>
  |     |           |
  |     |           +-- <term>
  |     |           |     |
  |     |           |     +-- <factor>
  |     |           |           |
  |     |           |           +-- '12'  (number)
  |     |           |      
  |     |           +-- '+'
  |     |           |
  |     |           +-- <term>
  |     |           |     |
  |     |           |     +-- <factor>
  |     |           |     |     |
  |     |           |     |     +-- '3'  (number)
  |     |           |     |
  |     |           |     +-- '*'
  |     |           |     |
  |     |           |     +-- <factor>
  |     |           |           |
  |     |           |           +-- '4'  (number)
  |     |           |     
  |     |           |
  |     |           |
  |     |           +-- ')'
  |     |
  |     +-- '/'
  |     |
  |     +-- <factor>
  |           |
  |           +-- '4'  (number)
  |
  +-- ')'