Рубрики

Выражение Оценка

Оценить выражение, представленное строкой. Выражение может содержать круглые скобки, вы можете предположить, что круглые скобки хорошо совпадают. Для простоты можно предположить, что допустимы только двоичные операции: +, -, * и /. Арифметические выражения могут быть записаны в одной из трех форм:

Нотация инфикса: операторы записываются между операндами, с которыми они работают, например, 3 + 4.

Обозначение префикса: операторы пишутся перед операндами, например, + 3 4

1. While there are still tokens to be read in,
   1.1 Get the next token.
   1.2 If the token is:
       1.2.1 A number: push it onto the value stack.
       1.2.2 A variable: get its value, and push onto the value stack.
       1.2.3 A left parenthesis: push it onto the operator stack.
       1.2.4 A right parenthesis:
         1 While the thing on top of the operator stack is not a 
           left parenthesis,
             1 Pop the operator from the operator stack.
             2 Pop the value stack twice, getting two operands.
             3 Apply the operator to the operands, in the correct order.
             4 Push the result onto the value stack.
         2 Pop the left parenthesis from the operator stack, and discard it.
       1.2.5 An operator (call it thisOp):
         1 While the operator stack is not empty, and the top thing on the
           operator stack has the same or greater precedence as thisOp,
           1 Pop the operator from the operator stack.
           2 Pop the value stack twice, getting two operands.
           3 Apply the operator to the operands, in the correct order.
           4 Push the result onto the value stack.
         2 Push thisOp onto the operator stack.
2. While the operator stack is not empty,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
3. At this point the operator stack should be empty, and the value
   stack should have only one value in it, which is the final result.

Должно быть ясно, что этот алгоритм работает за линейное время — каждый номер или оператор помещается в стек и извлекается из стека только один раз. Также см. Http://www2.lawrence.edu/fast/GREGGJ/CMSC270/Infix.html ,
http://faculty.cs.niu.edu/~hutchins/csci241/eval.htm .

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

C ++

// Программа CPP для оценки заданного
// выражение, где находятся токены
// разделены пробелом.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска приоритета
// операторы.

int precedence(char op){

    if(op == '+'||op == '-')

    return 1;

    if(op == '*'||op == '/')

    return 2;

    return 0;

}

  
// Функция для выполнения арифметических операций.

int applyOp(int a, int b, char op){

    switch(op){

        case '+': return a + b;

        case '-': return a - b;

        case '*': return a * b;

        case '/': return a / b;

    }

}

  
// Функция, которая возвращает значение
// выражение после оценки.

int evaluate(string tokens){

    int i;

      

    // стек для хранения целочисленных значений.

    stack <int> values;

      

    // стек для хранения операторов.

    stack <char> ops;

      

    for(i = 0; i < tokens.length(); i++){

          

        // Текущий токен является пробелом,

        // пропусти это.

        if(tokens[i] == ' ')

            continue;

          

        // Текущий токен является открытием

        // скобка, нажмите на «ops»

        else if(tokens[i] == '('){

            ops.push(tokens[i]);

        }

          

        // Текущий токен это число, push

        // это стек для чисел.

        else if(isdigit(tokens[i])){

            int val = 0;

              

            // Может быть больше одного

            // цифры в номере.

            while(i < tokens.length() && 

                        isdigit(tokens[i]))

            {

                val = (val*10) + (tokens[i]-'0');

                i++;

            }

              

            values.push(val);

        }

          

        // С закрывающей фигурной скобкой решаем

        // вся скобка.

        else if(tokens[i] == ')')

        {

            while(!ops.empty() && ops.top() != '(')

            {

                int val2 = values.top();

                values.pop();

                  

                int val1 = values.top();

                values.pop();

                  

                char op = ops.top();

                ops.pop();

                  

                values.push(applyOp(val1, val2, op));

            }

              

            // открываем открывающую скобку.

            if(!ops.empty())

               ops.pop();

        }

          

        // Текущий токен является оператором.

        else

        {

            // Хотя вершина 'ops' имеет то же или большее значение

            // приоритет текущего токена, который

            // это оператор. Применить оператор сверху

            // из 'ops' для двух верхних элементов в стеке значений.

            while(!ops.empty() && precedence(ops.top())

                                >= precedence(tokens[i])){

                int val2 = values.top();

                values.pop();

                  

                int val1 = values.top();

                values.pop();

                  

                char op = ops.top();

                ops.pop();

                  

                values.push(applyOp(val1, val2, op));

            }

              

            // Переместить текущий токен в «ops».

            ops.push(tokens[i]);

        }

    }

      

    // При этом было проанализировано все выражение

    // указать, применить оставшиеся операции к оставшимся

    // ценности.

    while(!ops.empty()){

        int val2 = values.top();

        values.pop();

                  

        int val1 = values.top();

        values.pop();

                  

        char op = ops.top();

        ops.pop();

                  

        values.push(applyOp(val1, val2, op));

    }

      

    // Вершина значений содержит результат, возвращает его.

    return values.top();

}

  

int main() {

    cout << evaluate("10 + 2 * 6") << "\n";

    cout << evaluate("100 * 2 + 12") << "\n";

    cout << evaluate("100 * ( 2 + 12 )") << "\n";

    cout << evaluate("100 * ( 2 + 12 ) / 14");

    return 0;

}

  
// Этот код предоставлен Nikhil jindal.

Джава

/ * Java-программа для оценки заданного выражения, где токены разделены

   по космосу.

   Тестовые случаи:

     "10 + 2 * 6" ---> 22

     "100 * 2 + 12" ---> 212

     «100 * (2 + 12)» ---> 1400

     "100 * (2 + 12) / 14" ---> 100

* / 

import java.util.Stack;

  

public class EvaluateString

{

    public static int evaluate(String expression)

    {

        char[] tokens = expression.toCharArray();

  

         // Стек для чисел: 'значения'

        Stack<Integer> values = new Stack<Integer>();

  

        // Стек для операторов: 'ops'

        Stack<Character> ops = new Stack<Character>();

  

        for (int i = 0; i < tokens.length; i++)

        {

             // Текущий токен является пробелом, пропустите его

            if (tokens[i] == ' ')

                continue;

  

            // Текущий токен - это число, помещаем его в стек для чисел

            if (tokens[i] >= '0' && tokens[i] <= '9')

            {

                StringBuffer sbuf = new StringBuffer();

                // В номере может быть несколько цифр

                while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')

                    sbuf.append(tokens[i++]);

                values.push(Integer.parseInt(sbuf.toString()));

            }

  

            // Текущий токен является открывающей фигурной скобкой, переводим его в 'ops'

            else if (tokens[i] == '(')

                ops.push(tokens[i]);

  

            // Закрытая фигурная скобка, решить всю фигурную скобку

            else if (tokens[i] == ')')

            {

                while (ops.peek() != '(')

                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));

                ops.pop();

            }

  

            // Текущий токен является оператором.

            else if (tokens[i] == '+' || tokens[i] == '-' ||

                     tokens[i] == '*' || tokens[i] == '/')

            {

                // Хотя top of 'ops' имеет такой же или больший приоритет перед текущим

                // токен, который является оператором. Применить оператор поверх 'ops'

                // на вершину двух элементов в стеке значений

                while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))

                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));

  

                // Переместить текущий токен в «ops».

                ops.push(tokens[i]);

            }

        }

  

        // На этом этапе было проанализировано все выражение, применить оставшееся

        // ops для оставшихся значений

        while (!ops.empty())

            values.push(applyOp(ops.pop(), values.pop(), values.pop()));

  

        // вершина значений содержит результат, возвращает его

        return values.pop();

    }

  

    // Возвращает true, если 'op2' имеет более высокий или тот же приоритет, что и 'op1',

    // в противном случае возвращает false.

    public static boolean hasPrecedence(char op1, char op2)

    {

        if (op2 == '(' || op2 == ')')

            return false;

        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))

            return false;

        else

            return true;

    }

  

    // Служебный метод для применения оператора 'op' к операндам 'a'

    // и 'b'. Вернуть результат.

    public static int applyOp(char op, int b, int a)

    {

        switch (op)

        {

        case '+':

            return a + b;

        case '-':

            return a - b;

        case '*':

            return a * b;

        case '/':

            if (b == 0)

                throw new

                UnsupportedOperationException("Cannot divide by zero");

            return a / b;

        }

        return 0;

    }

  

    // Метод драйвера для тестирования вышеуказанных методов

    public static void main(String[] args)

    {

        System.out.println(EvaluateString.evaluate("10 + 2 * 6"));

        System.out.println(EvaluateString.evaluate("100 * 2 + 12"));

        System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));

        System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));

    }

}

python3

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

  
# Функция для поиска приоритета
Количество операторов.

def precedence(op):

      

    if op == '+' or op == '-':

        return 1

    if op == '*' or op == '/':

        return 2

    return 0

  
# Функция для выполнения арифметики
# операции.

def applyOp(a, b, op):

      

    if op == '+': return a + b

    if op == '-': return a - b

    if op == '*': return a * b

    if op == '/': return a // b

  
# Функция, которая возвращает значение
# выражение после оценки.

def evaluate(tokens):

      

    # стек для хранения целочисленных значений.

    values = []

      

    # стек для хранения операторов.

    ops = []

    i = 0

      

    while i < len(tokens):

          

        # Текущий токен является пробелом,

        # пропусти это.

        if tokens[i] == ' ':

            i += 1

            continue

          

        # Текущий токен является открытием

        # скобка, толкни его на «ops»

        elif tokens[i] == '(':

            ops.append(tokens[i])

          

        # Текущий токен - это число, нажмите

        # это складывать для чисел.

        elif tokens[i].isdigit():

            val = 0

              

            # Может быть больше одного

            # цифры в номере.

            while (i < len(tokens) and

                tokens[i].isdigit()):

              

                val = (val * 10) + int(tokens[i])

                i += 1

              

            values.append(val)

          

        # Встречается закрывающая скобка,

        # решить всю скобку.

        elif tokens[i] == ')':

          

            while len(ops) != 0 and ops[-1] != '(':

              

                val2 = values.pop()

                val1 = values.pop()

                op = ops.pop()

                  

                values.append(applyOp(val1, val2, op))

              

            # поп открывающая скобка.

            ops.pop()

          

        # Текущий токен является оператором.

        else:

          

            # В то время как вершина 'ops' имеет то же самое или

            # больший приоритет по сравнению с текущим

            # токен, который является оператором.

            # Применить оператор поверх 'ops'

            # наверх двух элементов в стеке значений.

            while (len(ops) != 0 and

                precedence(ops[-1]) >= precedence(tokens[i])):

                          

                val2 = values.pop()

                val1 = values.pop()

                op = ops.pop()

                  

                values.append(applyOp(val1, val2, op))

              

            # Нажмите текущий токен на «ops».

            ops.append(tokens[i])

          

        i += 1

      

    # Все выражение было проанализировано

    # в этот момент примените оставшиеся операции

    # до оставшихся значений.

    while len(ops) != 0:

          

        val2 = values.pop()

        val1 = values.pop()

        op = ops.pop()

                  

        values.append(applyOp(val1, val2, op))

      

    # В верхней части 'values' содержится результат,

    # верни это.

    return values[-1]

  
Код водителя

if __name__ == "__main__":

      

    print(evaluate("10 + 2 * 6"))

    print(evaluate("100 * 2 + 12"))

    print(evaluate("100 * ( 2 + 12 )"))

    print(evaluate("100 * ( 2 + 12 ) / 14"))

  
# Этот код добавлен
# Ритурай Джайн

C #

/ * AC # программа для оценки заданного выражения, где токены разделены

   по космосу.

   Тестовые случаи:

     "10 + 2 * 6" ---> 22

     "100 * 2 + 12" ---> 212

     «100 * (2 + 12)» ---> 1400

     "100 * (2 + 12) / 14" ---> 100

* / 

using System;

using System.Collections.Generic;

using System.Text;

  

public class EvaluateString

{

    public static int evaluate(string expression)

    {

        char[] tokens = expression.ToCharArray();

  

         // Стек для чисел: 'значения'

        Stack<int> values = new Stack<int>();

  

        // Стек для операторов: 'ops'

        Stack<char> ops = new Stack<char>();

  

        for (int i = 0; i < tokens.Length; i++)

        {

             // Текущий токен является пробелом, пропустите его

            if (tokens[i] == ' ')

            {

                continue;

            }

  

            // Текущий токен - это число, помещаем его в стек для чисел

            if (tokens[i] >= '0' && tokens[i] <= '9')

            {

                StringBuilder sbuf = new StringBuilder();

                // В номере может быть несколько цифр

                while (i < tokens.Length && tokens[i] >= '0' && tokens[i] <= '9')

                {

                    sbuf.Append(tokens[i++]);

                }

                values.Push(int.Parse(sbuf.ToString()));

            }

  

            // Текущий токен является открывающей фигурной скобкой, переводим его в 'ops'

            else if (tokens[i] == '(')

            {

                ops.Push(tokens[i]);

            }

  

            // Закрытая фигурная скобка, решить всю фигурную скобку

            else if (tokens[i] == ')')

            {

                while (ops.Peek() != '(')

                {

                  values.Push(applyOp(ops.Pop(), values.Pop(), values.Pop()));

                }

                ops.Pop();

            }

  

            // Текущий токен является оператором.

            else if (tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/')

            {

                // Хотя top of 'ops' имеет такой же или больший приоритет перед текущим

                // токен, который является оператором. Применить оператор поверх 'ops'

                // на вершину двух элементов в стеке значений

                while (ops.Count > 0 && hasPrecedence(tokens[i], ops.Peek()))

                {

                  values.Push(applyOp(ops.Pop(), values.Pop(), values.Pop()));

                }

  

                // Переместить текущий токен в «ops».

                ops.Push(tokens[i]);

            }

        }

  

        // На этом этапе было проанализировано все выражение, применить оставшееся

        // ops для оставшихся значений

        while (ops.Count > 0)

        {

            values.Push(applyOp(ops.Pop(), values.Pop(), values.Pop()));

        }

  

        // вершина значений содержит результат, возвращает его

        return values.Pop();

    }

  

    // Возвращает true, если 'op2' имеет более высокий или тот же приоритет, что и 'op1',

    // в противном случае возвращает false.

    public static bool hasPrecedence(char op1, char op2)

    {

        if (op2 == '(' || op2 == ')')

        {

            return false;

        }

        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))

        {

            return false;

        }

        else

        {

            return true;

        }

    }

  

    // Служебный метод для применения оператора 'op' к операндам 'a'

    // и 'b'. Вернуть результат.

    public static int applyOp(char op, int b, int a)

    {

        switch (op)

        {

        case '+':

            return a + b;

        case '-':

            return a - b;

        case '*':

            return a * b;

        case '/':

            if (b == 0)

            {

                throw new System.NotSupportedException("Cannot divide by zero");

            }

            return a / b;

        }

        return 0;

    }

  

    // Метод драйвера для тестирования вышеуказанных методов

    public static void Main(string[] args)

    {

        Console.WriteLine(EvaluateString.evaluate("10 + 2 * 6"));

        Console.WriteLine(EvaluateString.evaluate("100 * 2 + 12"));

        Console.WriteLine(EvaluateString.evaluate("100 * ( 2 + 12 )"));

        Console.WriteLine(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));

    }

}

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

Выход:

22
212
1400
100

Сложность времени: O (n)
Космическая сложность: O (n)

Смотрите это для примера выполнения с большим количеством тестов.

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

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

Выражение Оценка

0.00 (0%) 0 votes