Подтвердить что ты не робот

Оценка арифметических выражений из строки в С++

Я ищу простой способ оценить простое математическое выражение из строки, например:

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

Мне просто нужны + и * операции плюс ( и ). И * имеет больший приоритет, чем +.

4b9b3361

ОТВЕТЫ

Ответ 1

Я думаю, вы ищете простой рекурсивный парсер спуска.

Вот очень простой пример:

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;
}

Ответ 3

Просто, чтобы добавить другую альтернативу, попробуйте TinyExpr для этой проблемы. Он с открытым исходным кодом и самодостаточен в одном файле исходного кода. На самом деле он написан на C, но по моему опыту он будет скомпилирован как C++.

Решение вашего примера выражения сверху так же просто, как:

#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;
}

Ответ 4

При поиске в библиотеке для подобной задачи я нашел libmatheval. Кажется, это правильная вещь. К сожалению, GPL, что неприемлемо для меня.

Ответ 5

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)));
    }
}

Ответ 6

Я написал очень простой оценщик выражений в С# (минимальные изменения, необходимые для обеспечения совместимости с С++). Он основан на методе построения дерева выражений, только это дерево фактически не построено, но все узлы оцениваются на месте.

Вы можете найти его по этому адресу: Простой арифметический экзаменатор

Ответ 7

Поэтому я искал ответ на этот вопрос. И я пытался создать свой собственный язык программирования. Для математических выражений мне была нужна эта функция.

Ок, дай, я дам тебе. Используйте это так, как вы хотите.

/* Code here before is useless now */

Это довольно долгий и, вероятно, неэффективный способ решения такой задачи. Но работа сделана, так что дерзайте. Вскоре я планирую добавить поддержку переменных. Но вы тоже можете это сделать, это довольно легко (я полагаю: P).

РЕДАКТИРОВАТЬ: я только прибрал функцию, теперь она работает как волшебный XD..

using namespace std;

double eval(string expr)
{
    string xxx; // Get Rid of Spaces
    for (int i = 0; i < expr.length(); i++)
    {
        if (expr[i] != ' ')
        {
            xxx += expr[i];
        }
    }

    string tok = ""; // Do parantheses first
    for (int i = 0; i < xxx.length(); i++)
    {
        if (xxx[i] == '(')
        {
            int iter = 1;
            string token;
            i++;
            while (true)
            {
                if (xxx[i] == '(')
                {
                    iter++;
                } else if (xxx[i] == ')')
                {
                    iter--;
                    if (iter == 0)
                    {
                        i++;
                        break;
                    }
                }
                token += xxx[i];
                i++;
            }
            //cout << "(" << token << ")" << " == " << to_string(eval(token)) <<  endl;
            tok += to_string(eval(token));
        }
        tok += xxx[i];
    }

    for (int i = 0; i < tok.length(); i++)
    {
        if (tok[i] == '+')
        {
            //cout << tok.substr(0, i) + " + " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) + eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) + eval(tok.substr(i+1, tok.length()-i-1));
        } else if (tok[i] == '-')
        {
            //cout << tok.substr(0, i) + " - " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) - eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) - eval(tok.substr(i+1, tok.length()-i-1));
        }
    }

    for (int i = 0; i < tok.length(); i++)
    {
        if (tok[i] == '*')
        {
            //cout << tok.substr(0, i) + " * " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) * eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) * eval(tok.substr(i+1, tok.length()-i-1));
        } else if (tok[i] == '/')
        {
            //cout << tok.substr(0, i) + " / " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) / eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) / eval(tok.substr(i+1, tok.length()-i-1));
        }
    }

    //cout << stod(tok.c_str()) << endl;
    return stod(tok.c_str()); // Return the value...
}