Đánh giá biểu thức số học từ chuỗi trong C++

Question

Tôi đang tìm kiếm một cách đơn giản để đánh giá một biểu thức toán học đơn giản từ một chuỗi, như thế này:

3 * 2 + 4 * 1 + (4 + 9) * 6

tôi chỉ muốn + và * hoạt động cộng ( và ) dấu hiệu. Và * có mức độ ưu tiên cao hơn +.

Answer 1

Tôi nghĩ rằng bạn đang tìm kiếm một đơn giản recursive descent parser.

Dưới đây là một ví dụ rất đơn giản:

const char * expressionToParse = "3*2+4*1+(4+9)*6"; 

char peek() 
{ 
    return *expressionToParse; 
} 

char get() 
{ 
    return *expressionToParse++; 
} 

int expression(); 

int number() 
{ 
    int result = get() - '0'; 
    while (peek() >= '0' && peek() <= '9') 
    { 
     result = 10*result + get() - '0'; 
    } 
    return result; 
} 

int factor() 
{ 
    if (peek() >= '0' && peek() <= '9') 
     return number(); 
    else if (peek() == '(') 
    { 
     get(); // '(' 
     int result = expression(); 
     get(); // ')' 
     return result; 
    } 
    else if (peek() == '-') 
    { 
     get(); 
     return -factor(); 
    } 
    return 0; // error 
} 

int term() 
{ 
    int result = factor(); 
    while (peek() == '*' || peek() == '/') 
     if (get() == '*') 
      result *= factor(); 
     else 
      result /= factor(); 
    return result; 
} 

int expression() 
{ 
    int result = term(); 
    while (peek() == '+' || peek() == '-') 
     if (get() == '+') 
      result += term(); 
     else 
      result -= term(); 
    return result; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 

    int result = expression(); 

    return 0; 
} 

Answer 2

Tôi nghĩ rằng bạn có thể tìm thấy câu trả lời trong bài viết này: Evaluating string "3*(4+2)" yield int 18

Hoặc bạn có thể đưa ra một thử vào thư viện này: http://weblogs.asp.net/pwelter34/archive/2007/05/05/calculator-net-calculator-that-evaluates-math-expressions.aspx

Answer 3

Xem xét sử dụng tinh thần tăng:

http://www.boost.org/doc/libs/1_35_0/libs/spirit/example/fundamental/ast_calc.cpp

Answer 4

Dưới đây là một bài thuyết trình tốt đẹp chút trên cây đánh giá cho phức tạp (không thực sự: p) biểu thức toán học:

http://courses.cs.vt.edu/~cs1044/spring01/cstruble/notes/6.complexexpr.pdf

Nó sẽ hướng dẫn bạn qua nó theo phong cách;)

Answer 5

Tôi đã viết một biểu thức đánh giá rất đơn giản trong C# (tối thiểu thay đổi cần thiết để làm cho nó phù hợp với C++). Nó dựa trên phương thức xây dựng cây biểu thức, chỉ có cây đó không thực sự được xây dựng nhưng tất cả các nút được đánh giá tại chỗ.

Bạn có thể tìm thấy nó trên địa chỉ này: Simple Arithmetic Expression Evaluator

Answer 6

Trong khi tìm kiếm một thư viện cho một nhiệm vụ tương tự như tôi thấy libmatheval. Có vẻ là một điều thích hợp. Thật không may, GPL, đó là không thể chấp nhận đối với tôi.

Answer 7

import java.util.Deque; 
import java.util.LinkedList; 


public class EvaluateArithmeticExpression { 
    public static void main(String[] args) { 
     System.out.println(evaluate("-4*2/2^3+3")==-4*2/Math.pow(2, 3)+3); 
     System.out.println(evaluate("12*1314/(1*4)+300")==12*1314/(1*4)+300); 
     System.out.println(evaluate("123-(14*4)/4+300")==123-(14*4)/4+300); 
     System.out.println(evaluate("12*4+300")==12*4+300); 
    } 
    public static int evaluate(String s){ 
     Deque<Integer> vStack= new LinkedList<>(); 
     Deque<Character> opStack= new LinkedList<>(); 
     int i=0; 
     while(i<s.length()){ 
      if(isNum(s,i)) 
       i=getNum(s,vStack,i); 
      else if(isOp(s,i)) 
       i=doOp(s,opStack,vStack,i); 
     } 
     doOp(opStack,vStack); 
     return vStack.pop(); 
    } 
    private static int getNum(String s, Deque<Integer> vStack,int i){ 
     int sign=1; 
     if(s.charAt(i)=='-' || s.charAt(i)=='+') 
      sign=s.charAt(i++)=='-'?-1:1; 
     int val=0; 
     while(i<s.length() && isNum(s,i)) 
      val=val*10+s.charAt(i++)-'0'; 
     vStack.push(sign*val); 
     return i; 
    } 
    private static int doOp(String s, Deque<Character> opStack,Deque<Integer> vStack,int i){ 
     char op=s.charAt(i); 
     if(op=='(') 
      opStack.push(op); 
     else{ 
      if(op==')'){ 
       while(!opStack.isEmpty() && opStack.peekFirst()!='(') 
        doOp(opStack,vStack); 
       opStack.pop(); 
      } 
      else{ 
       while(!opStack.isEmpty() && prior(op)<=prior(opStack.peekFirst())) 
        doOp(opStack,vStack); 
       opStack.push(op); 
      } 
     } 
     return i+1; 
    } 
    private static int prior(char op){ 
     switch(op){ 
      case '+': 
      case '-': return 1; 
      case '*': 
      case '/': return 2; 
      case '^': return 4; 
     } 
     return 0; 
    } 
    private static void doOp(Deque<Character> opStack,Deque<Integer> vStack){ 
     int b=vStack.isEmpty()?0:vStack.pop(); 
     int a=vStack.isEmpty()?0:vStack.pop(); 
     char op=opStack.pop(); 
     int res=evaluate(a,b,op); 
     vStack.push(res); 
    } 
    private static int evaluate(int a, int b, char op){ 
     switch(op){ 
      case '+': return a+b; 
      case '-': return a-b; 
      case '/': return a/b; 
      case '*': return a*b; 
      case '^': return (int)Math.pow(a,b); 
     } 
     return 0; 
    } 
    private static boolean isNum(String s, int i){ 
     return '0'<=s.charAt(i) && s.charAt(i)<='9'; 
    } 
    private static boolean isOp(String s, int i){ 
     return "()+-*/^".contains(String.valueOf(s.charAt(i))); 
    } 
} 

Answer 8

Người ta có thể thử: http://partow.net/programming/exprtk/index.html

1. rất đơn giản
2. chỉ cần bao gồm "exprtk.hpp" vào mã nguồn của bạn.
3. bạn có thể thay đổi giá trị của các biến của biểu thức động.
4. tốt điểm khởi đầu: http://partow.net/programming/exprtk/code/exprtk_simple_example_01.cpp

Answer 9

Chỉ cần thêm lựa chọn khác, hãy xem xét cố gắng TinyExpr cho vấn đề này. Đó là mã nguồn mở và tự chứa trong một tệp mã nguồn. Nó thực sự được viết bằng C, nhưng nó sẽ biên dịch rõ ràng như C++ trong kinh nghiệm của tôi.

Giải quyết biểu ví dụ của bạn từ trên cao cũng đơn giản như:

#include "tinyexpr.h" 
#include <stdio.h> 

int main() 
{ 
    double answer = te_interp("3*2+4*1+(4+9)*6", 0); 
    printf("Answer is %f\n", answer); 
    return 0; 
}