評估一個簡單的字符串數學表達式

Question

我剛剛參加了以下問題的研究生C++開發人員的測試。它沒有做得太好，因爲我無法確定完成任務的明確方式。時間限制也沒有幫助。我感興趣的是如何經驗的開發人員會解決後續問題 - 僞或示例代碼：

Evaluate 

Write a function in C or C++ that evaluates the result of a simple expression. 
The function should ignore whitespace, but stop at the first non valid character. 
Valid tokens are listed in the table below: 

0-9 - Only integers are allowed in expressions 

() - Nested expressions should be evaluated first. 

+, -, *,/- Basic operators are addition, subtraction, multiplication and division. 

The expression should be parsed from left to right. It is not necessary to consider operator precedence in your solution (e.g. 1 + 3 * 4 = 16). If there is an error in the expression, the function should return false. 

Suggested prototype for function: 

Example: 

bool evaluate(const char *expression, int &result) 
{ 
... 
} 

**Input** 
1+3 
(1 + (12 * 2) 

**Result** 
4 
N/A 

**Return code** 
true 
false (missing bracket) 

此外，這是第二個C++，我已經未能成功完成。使用C++已經有1年的跨學科經驗和1年的學術經驗，但我沒有準備好進行這些測試。有沒有推薦的資源可以幫助我解決諸如此類問題，以獲得更多的「測試」體驗？

Answer 1

這裏的問題主要是解析，這可能會在第二年或第三年編譯器課程中介紹。一旦你可以解析表達式來構建一個代表輸入的遞歸數據結構（稱爲語法樹），評估這樣的表達式就相當簡單了。遞歸體面分析器也可以在不實際構建語法樹的情況下評估表達式。

對於一個完整的治療，你會想要一本關於編譯器的書，比如龍書。另外IIRC的書編程：使用C++的校長和實踐涵蓋了一個這樣的例子。

您還可以等待第十章的計算機編程藝術發佈，其中將包括解析。它計劃在2020年前後出現。

Answer 2

解決（不一定）簡單數學表達式的最簡單方法是使用Shunting Yard algorithm將其轉換爲Reverse Polish Notation，這對於使用堆棧進行解析幾乎是微不足道的。當然，對於任務或面試來說這樣做可能是不可行的（也許除非有一個SY算法參考可用）。

Answer 3

這是我最短的嘗試。花了大約40分鐘打字，你可以在ideone上玩（link）。

該代碼非常簡單，假設您至少對基本recursive descent parsing技術有一個粗略的熟悉。

#include <iostream> 
#include <cctype> 
using namespace std; 
bool eval_expr(const char **pe, int &lhs, bool inside = false); 
// gets the next char after skipping optional whitespace 
char skip_ws(const char **pe) { 
    while (**pe == ' ') ++(*pe); 
    return **pe; 
} 
// evaluates a parenthesized expression or a number 
bool eval_prim(const char **pe, int &res) { 
    char c = skip_ws(pe); 
    if (c == '(') { 
     ++(*pe); 
     if (!eval_expr(pe, res, true)) return false; 
     ++(*pe); 
     return true; 
    } 
    if (isdigit(c)) { 
     res = 0; 
     while (isdigit(c)) { 
      res = 10*res + c - '0'; 
      c = *(++(*pe)); 
     } 
     return true; 
    } 
    return false; 
} 
// evaluates a chain of + - */operations 
bool eval_expr(const char **pe, int &lhs, bool inside) { 
    if (!eval_prim(pe, lhs)) return false; 
    char op; 
    while ((op = skip_ws(pe)) && (op == '+' || op == '-' || op == '*' || op == '/')) { 
     ++(*pe); 
     int rhs; 
     if (!eval_prim(pe, rhs)) return false; 
     switch (op) { 
      case '+': lhs += rhs; break; 
      case '-': lhs -= rhs; break; 
      case '*': lhs *= rhs; break; 
      case '/': lhs /= rhs; break; 
     } 
    } 
    return inside ? op == ')' : !op; 
} 
// wrapper API to hide an extra level of indirection 
bool evaluate(const char *e, int &result) { 
    return eval_expr(&e, result); 
} 

Answer 4

這是一個簡單的掃描推適用（扭曲是大括號）。

1. 查找一個數字：
   • 如果你看到一些推入堆棧
   • 如果你看到一個「（」推入堆棧和轉到1
   • 否則錯誤。
2. 查找運算：
   • 如果你看到一個運算推到堆棧
   • 否則錯誤
3. 查找一個數字：
   • 如果你看到一個數字推入堆棧
   • 如果您看到'（'推入堆棧並且轉到1
   • 否則錯誤
4. 彈出過去三年從棧中的項目（應該是數字運算次數）
   
   • 做了手術，結果壓入堆棧。
5. 現在複雜位：
   • 偷看，看是否下一個字符是一個「）」如果是轉到「Pop代碼」下方。
6. 如果不再輸入轉到7。
   • Otherewise 轉到2
7. 如果只有一個堆棧上的項目你有你的結果。
   • 否則會報錯。

Pop代碼

1. 流行過去兩年從堆棧值。應該是「（編號」
   • 如果它不是，則一個錯誤
2. 扔掉「（」
3. 如果堆棧的頂部是轉到4（以上運算推值）
4. 否則推值壓入堆棧轉到圖5（上圖）

完成時，應該有一個堆棧上一個號碼。

例子：

1+3 
Rule 1: push 1    stack = '1' 
Rule 2: push +    stack = '1 +' 
Rule 3: push 3    stack = '1 + 3' 
Rule 4: pop and do:  stack = '4' 
Rule 5: Nothing   stack = '4' 
Rule 6: goto 7    stack = '4' 
Rule 7:     stack = '4' 

(1 + (12 * 2) 
Rule 1: push (goto 1  stack = '(' 
Rule 1: push 1    stack = '(1' 
Rule 2: push +    stack = '(1 +' 
Rule 3: push (goto 1  stack = '(1 + (' 
Rule 1: push 12   stack = '(1 + (12' 
Rule 2: push *    stack = '(1 + (12 *' 
Rule 3: push 2    stack = '(1 + (12 * 2' 
Rule 4: Pop and do:  stack = '(1 + (24' 
Rule 5: Do 'PopCode'  stack = '(1 + (24' 
Pop 1: Pop 2    stack = '(1 +' 
Pop 2: Holding 24   stack = '(1 +' 
Pop 3: push 24 goto 4  stack = '(1 + 24' 
Rule 4: Pop and do   stack = '(25' 
Rule 5: Nothing   stack = '(25' 
Rule 6: goto 7    stacj = '(25' 
Rule 7: More than 1 item error 

Re-Doing with correct formula 
(1 + (12 * 2)) 
Rule 1: push (goto 1  stack = '(' 
Rule 1: push 1    stack = '(1' 
Rule 2: push +    stack = '(1 +' 
Rule 3: push (goto 1  stack = '(1 + (' 
Rule 1: push 12   stack = '(1 + (12' 
Rule 2: push *    stack = '(1 + (12 *' 
Rule 3: push 2    stack = '(1 + (12 * 2' 
Rule 4: Pop and do:  stack = '(1 + (24' 
Rule 5: Do 'PopCode'  stack = '(1 + (24' 
Pop 1: Pop 2    stack = '(1 +' 
Pop 2: Holding 24   stack = '(1 +' 
Pop 3: push 24 goto 4  stack = '(1 + 24' 
Rule 4: Pop and do   stack = '(25' 
Rule 5: Do 'PopCode'  stack = '(25' 
Pop 1: Pop 2    stack = '' 
Pop 2: holding 25   stack = '' 
Pop 3: Nothing.   stack = '' 
Pop 4: push 25 goto 5  stack = '25' 
Rule 5: Nothing   stack = '25' 
Rule 6: goto 7    stack = '25' 
Rule 7: Result = 25 

Answer 5

開始一個簡單的語法：

expr: n-expr {o-expr} | p-expr {o-expr} 
n-expr: [0-9]n-expr 
p-expr: (expr) 
o-expr: op expr 
op: + | - | * |/

這可能是問題的最大障礙。你希望能夠編寫一個簡單的自頂向下的遞歸下降解析器，所以你的語法需要以一種方式寫入，以允許這種情況發生。

然後從那裏實現是相當簡單：

bool expr (const char *&s, int &result, int eos = 0) { 
    while (isspace(*s)) ++s; 
    if (*s == eos) return false; 
    if (isdigit(*s)) { 
     if (!n_expr(s, result)) return false; 
    } else if (*s == '(') { 
     if (!p_expr(s, result)) return false; 
    } else return false; 
    while (isspace(*s)) ++s; 
    if (*s == eos) return true; 
    return o_expr(s, result, eos); 
} 

bool n_expr (const char *&s, int &result) { 
    int n = 0; 
    while (isdigit(*s)) n = 10 * n + (*s++ - '0'); 
    result = n; 
    return true; 
} 

bool p_expr (const char *&s, int &result) { 
    if (expr(++s, result, ')')) { 
     ++s; 
     return true; 
    } 
    return false; 
} 

bool o_expr (const char *&s, int &result, int eos) { 
    int oresult = 0; 
    const char *op = strchr("+-*/", *s); 
    if (op == 0) return false; 
    if (!expr(++s, oresult, eos)) return false; 
    switch (*op) { 
    case '+': result += oresult; break; 
    case '-': result -= oresult; break; 
    case '*': result *= oresult; break; 
    case '/': result /= oresult; break; 
    default: return false; 
    } 
    return true; 
}