Рубрики

Найти все возможные результаты данного выражения

Учитывая арифметическое выражение, найдите все возможные результаты этого выражения. Различные результаты оцениваются путем помещения скобок в разных местах.

Мы можем предположить, что числа являются однозначными числами в данном выражении.

Примеры:

Input:  1+3*2
Output: 8  7
Explanation
(1 + 3)*2     = 80
(1 + (3 * 2)) = 70

Input:  1*2+3*4
Output: 14 20 14 20 20
 (1*(2+(3*4))) =  14
 (1*((2+3)*4)) =  20 
 ((1*2)+(3*4)) =  14
 ((1*(2+3))*4) =  20
 ((1*2)+3)*4)  =  20

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

1) Initialize result 'res' as empty.
2) Do following for every operator 'x'.
    a) Recursively evaluate all possible values on left of 'x'.
       Let the list of values be 'l'.  
    a) Recursively evaluate all possible values on right of 'x'.
       Let the list of values be 'r'.
    c) Loop through all values in list 'l'  
           loop through all values in list 'r'
               Apply current operator 'x' on current items of 
               'l' and 'r' and add the evaluated value to 'res'   
3) Return 'res'.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для оценки всех возможных значений
// выражение
#include<bits/stdc++.h>

using namespace std;

  
// Сервисная функция для оценки простого выражения
// только с одним оператором.

int eval(int a, char op, int b)

{

    if (op=='+')   return a+b;

    if (op=='-')   return a-b;

    if (op == '*') return a*b;

}

  
// Эта функция оценивает все возможные значения и
// возвращает список оцененных значений.

vector<int> evaluateAll(string expr, int low, int high)

{

    // Для сохранения результата (все возможные оценки

    // данное выражение 'expr')

    vector<int> res;

  

    // Если есть только один символ, он должен

    // быть цифрой (или операндом), вернуть ее.

    if (low == high)

    {

        res.push_back(expr[low] - '0');

        return res;

    }

  

    // Если есть только три символа, середина

    // один должен быть оператором, а угловой должен быть

    // операнд

    if (low == (high-2))

    {

        int num = eval(expr[low]-'0', expr[low+1],

                       expr[low+2]-'0');

  

        res.push_back(num);

        return res;

    }

  

    // каждый я ссылается на оператора

    for (int i=low+1; i<=high; i+=2)

    {

        // l ссылается на все возможные значения

        // слева от оператора 'expr [i]'

        vector<int> l = evaluateAll(expr, low, i-1);

  

        // r ссылается на все возможные значения

        // справа от оператора 'expr [i]'

        vector<int> r = evaluateAll(expr, i+1, high);

  

        // Возьми выше оценил все возможное

        // значения в левой части 'i'

        for (int s1=0; s1<l.size(); s1++)

        {

            // Возьми выше оценил все возможное

            // значения в правой части 'i'

            for (int s2=0; s2<r.size(); s2++)

            {

                // Рассчитать значение для каждой пары

                // и добавляем значение к результату.

                int val = eval(l[s1], expr[i], r[s2]);

                res.push_back(val);

            }

        }

    }

    return res;

}

  
// Драйвер программы

int main()

{

    string expr = "1*2+3*4";

    int len = expr.length();

    vector<int> ans = evaluateAll(expr, 0, len-1);

  

    for (int i=0; i< ans.size(); i++)

        cout << ans[i] << endl;

  

    return 0;

}

Джава

// Java программа для оценки всего возможного
// значения выражения

import java.util.*;

  

class GFG 

{

  

    // Сервисная функция для оценки простого выражения

    // только с одним оператором.

    static int eval(int a, char op, int b) 

    {

        if (op == '+')

        {

            return a + b;

        }

        if (op == '-')

        {

            return a - b;

        }

        if (op == '*'

        {

            return a * b;

        }

        return Integer.MAX_VALUE;

    }

  

    // Эта функция оценивает все возможные значения и

    // возвращает список оцененных значений.

    static Vector<Integer> evaluateAll(String expr,

                                    int low, int high) 

    {

        // Для сохранения результата (все возможные оценки

        // данное выражение 'expr')

        Vector<Integer> res = new Vector<Integer>();

  

        // Если есть только один символ, он должен

        // быть цифрой (или операндом), вернуть ее.

        if (low == high) 

        {

            res.add(expr.charAt(low) - '0');

            return res;

        }

  

        // Если есть только три символа, середина

        // один должен быть оператором, а угловой должен быть

        // операнд

        if (low == (high - 2)) 

        {

            int num = eval(expr.charAt(low) - '0'

                         expr.charAt(low + 1),

                        expr.charAt(low + 2) - '0');

  

            res.add(num);

            return res;

        }

  

        // каждый я ссылается на оператора

        for (int i = low + 1; i <= high; i += 2

        {

              

            // l ссылается на все возможные значения

            // слева от оператора 'expr [i]'

            Vector<Integer> l = evaluateAll(expr, low, i - 1);

  

            // r ссылается на все возможные значения

            // справа от оператора 'expr [i]'

            Vector<Integer> r = evaluateAll(expr, i + 1, high);

  

            // Возьми выше оценил все возможное

            // значения в левой части 'i'

            for (int s1 = 0; s1 < l.size(); s1++) 

            {

                  

                // Возьми выше оценил все возможное

                // значения в правой части 'i'

                for (int s2 = 0; s2 < r.size(); s2++) 

                {

                      

                    // Рассчитать значение для каждой пары

                    // и добавляем значение к результату.

                    int val = eval(l.get(s1), expr.charAt(i), r.get(s2));

                    res.add(val);

                }

            }

        }

        return res;

    }

  

    // Драйвер программы

    public static void main(String[] args) 

    {

        String expr = "1*2+3*4";

        int len = expr.length();

        Vector<Integer> ans = evaluateAll(expr, 0, len - 1);

  

        for (int i = 0; i < ans.size(); i++) 

        {

            System.out.println(ans.get(i));

        }

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для оценки всех
# возможные значения выражения

  
# Функция полезности для оценки простого
# выражение только с одним оператором.

def eval(a, op, b): 

  

    if op == '+': return a +

    if op == '-': return a -

    if op == '*': return a *

  
# Эта функция оценивает все возможные значения
# и возвращает список оцененных значений.

def evaluateAll(expr, low, high): 

  

    # Сохранить результат (все возможно

    # оценки данного выражения 'expr')

    res = [] 

  

    # Если есть только один символ,

    # это должна быть цифра (или операнд),

    # верни это.

    if low == high: 

      

        res.append(int(expr[low])) 

        return res 

  

    # Если есть только три символа,

    # средний должен быть оператором и

    # угловые должны быть операндами

    if low == (high - 2): 

      

        num = eval(int(expr[low]), 

                       expr[low + 1], 

                   int(expr[low + 2])) 

  

        res.append(num) 

        return res 

  

    # каждый я ссылаюсь на оператора

    for i in range(low + 1, high + 1, 2): 

      

        # l относится ко всем возможным значениям

        # слева от оператора 'expr [i]'

        l = evaluateAll(expr, low, i - 1

  

        # r относится ко всем возможным значениям

        # в праве от оператора 'expr [i]'

        r = evaluateAll(expr, i + 1, high) 

  

        # Взять выше оценил все возможное

        # значения в левой части 'i'

        for s1 in range(0, len(l)): 

          

            # Взять выше оценил все возможное

            # значения в правой части 'i'

            for s2 in range(0, len(r)): 

              

                # Рассчитать значение для каждой пары

                # и добавьте значение к результату.

                val = eval(l[s1], expr[i], r[s2]) 

                res.append(val) 

      

    return res 

  
Код водителя

if __name__ == "__main__"

  

    expr = "1*2+3*4"

    length = len(expr) 

    ans = evaluateAll(expr, 0, length - 1

  

    for i in range(0, len(ans)):

        print(ans[i])

  
# Этот код предоставлен Rituraj Jain

C #

// C # программа для оценки всего возможного
// значения выражения

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Сервисная функция для оценки простого выражения

    // только с одним оператором.

    static int eval(int a, char op, int b) 

    {

        if (op == '+')

        {

            return a + b;

        }

        if (op == '-')

        {

            return a - b;

        }

        if (op == '*'

        {

            return a * b;

        }

        return int.MaxValue;

    }

  

    // Эта функция оценивает все возможные значения и

    // возвращает список оцененных значений.

    static List<int> evaluateAll(String expr,

                                    int low, int high) 

    {

        // Для сохранения результата (все возможные оценки

        // данное выражение 'expr')

        List<int> res = new List<int> ();

  

        // Если есть только один символ, он должен

        // быть цифрой (или операндом), вернуть ее.

        if (low == high) 

        {

            res.Add(expr[low] - '0');

            return res;

        }

  

        // Если есть только три символа, середина

        // один должен быть оператором, а угловой должен быть

        // операнд

        if (low == (high - 2)) 

        {

            int num = eval(expr[low] - '0'

                        expr[low + 1],

                        expr[low + 2] - '0');

  

            res.Add(num);

            return res;

        }

  

        // каждый я ссылается на оператора

        for (int i = low + 1; i <= high; i += 2) 

        {

              

            // l ссылается на все возможные значения

            // слева от оператора 'expr [i]'

            List<int> l = evaluateAll(expr, low, i - 1);

  

            // r ссылается на все возможные значения

            // справа от оператора 'expr [i]'

            List<int> r = evaluateAll(expr, i + 1, high);

  

            // Возьми выше оценил все возможное

            // значения в левой части 'i'

            for (int s1 = 0; s1 < l.Count; s1++) 

            {

                  

                // Возьми выше оценил все возможное

                // значения в правой части 'i'

                for (int s2 = 0; s2 < r.Count; s2++) 

                {

                      

                    // Рассчитать значение для каждой пары

                    // и добавляем значение к результату.

                    int val = eval(l[s1], expr[i], r[s2]);

                    res.Add(val);

                }

            }

        }

        return res;

    }

  

    // Код драйвера

    public static void Main() 

    {

        String expr = "1*2+3*4";

        int len = expr.Length;

        List<int> ans = evaluateAll(expr, 0, len - 1);

  

        for (int i = 0; i < ans.Count; i++) 

        {

            Console.WriteLine(ans[i]);

        }

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

PHP

<?php
// PHP программа для оценки всего возможного
// значения выражения

  
// Сервисная функция для оценки простого
// выражение только с одним оператором.

function eval1($a, $op, $b)

{

    if ($op == '+') return $a + $b;

    if ($op == '-') return $a - $b;

    if ($op == '*') return $a * $b;

}

  
// Эта функция вычисляет все возможные значения
// и возвращает список значений eval1uated.

function eval1uateAll($expr, $low, $high)

{

    // сохранить результат (все возможно

    // вычисления данного выражения 'expr')

    $res = array();

  

    // Если есть только один символ, он должен

    // быть цифрой (или операндом), вернуть ее.

    if ($low == $high)

    {

        array_push($res, ord($expr[$low]) - 

                         ord('0'));

        return $res;

    }

  

    // Если есть только три символа,

    // средний должен быть оператором и

    // угловые должны быть операндами

    if ($low == ($high - 2))

    {

        $num = eval1(ord($expr[$low]) - 

                     ord('0'), $expr[$low + 1],

                     ord($expr[$low + 2]) - 

                     ord('0'));

  

        array_push($res, $num);

        return $res;

    }

  

    // каждый я ссылается на оператора

    for ($i = $low + 1; $i <= $high; $i += 2)

    {

        // l ссылается на все возможные значения

        // слева от оператора 'expr [i]'

        $l = eval1uateAll($expr, $low, $i - 1);

  

        // r ссылается на все возможные значения

        // справа от оператора 'expr [i]'

        $r = eval1uateAll($expr, $i + 1, $high);

  

        // Взять выше eval1uated все возможное

        // значения в левой части 'i'

        for ($s1 = 0; $s1 < count($l); $s1++)

        {

            // Взять выше eval1uated все возможное

            // значения в правой части 'i'

            for ($s2 = 0; $s2 < count($r); $s2++)

            {

                // Рассчитать значение для каждой пары

                // и добавляем значение к результату.

                $val = eval1($l[$s1], 

                             $expr[$i], $r[$s2]);

                array_push($res, $val);

            }

        }

    }

    return $res;

}

  
// Код драйвера

$expr = "1*2+3*4";

$len = strlen($expr);

$ans = eval1uateAll($expr, 0, $len - 1);

  

for ($i = 0; $i < count($ans); $i++)

    echo $ans[$i] . "\n";

  
// Этот код предоставлен mits
?>


Выход:

14
20
14
20
20

Упражнение: Расширьте приведенное выше решение, чтобы оно работало и для чисел с несколькими цифрами. Например, выражения типа «100 * 30 + 20» (подсказка: мы можем создать целочисленный массив для хранения всех операндов и операторов данного выражения).

Эта статья предоставлена Ekta Goel . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти все возможные результаты данного выражения

0.00 (0%) 0 votes