Алгоритм Маневрового двора C ++

Question

Я написал попытку Алгоритма маневрового двора Дейкстры как часть проекта колледжа.Все работает, как и ожидалось, но я также должен показать последовательность операторов после процесса, и я не уверен, как это сделать, я считаю, что лучший способ сделать это - Очередь?У кого-нибудь есть идеи, как это можно сделать?Мой код:

// Finding operators 
int operators(char op){ 
    if(op == '+'||op == '-') 
    return 1; 
    if(op == '*'||op == '/') 
    return 2; 
    return 0; 
} 

// The maths
int maths(int a, int b, char op){ 
    switch(op){ 
        case '+': return a + b; 
        case '-': return a - b; 
        case '*': return a * b; 
        case '/': return a / b; 
    } 
  return 0;
} 

// Returning value of expression
int evaluate(string tokens){ 
    int i; 

    // stack to store integers and operators. 
    stack <int> numbers;  
    stack <char> ops; 

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

        // if token blank, skip 
        if(tokens[i] == ' ') 
            continue; 

        // if token '(' add to stack
        else if(tokens[i] == '('){ 
            ops.push(tokens[i]); 
        } 

        // if token is a number, add to stack
        else if(isdigit(tokens[i])){ 
            int val = 0; 

            // single or double digit number.
            while(i < tokens.length() && 
                        isdigit(tokens[i])) 
            { 
                val = (val*10) + (tokens[i]-'0'); 
                i++; 
            } 

            numbers.push(val); 
        } 

        // if token ')', solve entire brace. 
        else if(tokens[i] == ')') 
        { 
            while(!ops.empty() && ops.top() != '(') 
            { 
                int val2 = numbers.top(); 
                numbers.pop(); 

                int val1 = numbers.top(); 
                numbers.pop(); 

                char op = ops.top(); 
                ops.pop(); 

                numbers.push(maths(val1, val2, op)); 
            } 

            // pop opening brace. 
            ops.pop(); 
        } 

        // Current token is an operator. 
        else
        { 

            while(!ops.empty() && operators(ops.top()) 
                                >= operators(tokens[i])){ 
                int val2 = numbers.top(); 
                numbers.pop(); 

                int val1 = numbers.top(); 
                numbers.pop(); 

                char op = ops.top(); 
                ops.pop(); 

                numbers.push(maths(val1, val2, op)); 
            } 

            // Push current token to 'ops'. 
            ops.push(tokens[i]); 
        } 
    } 

    //Do remaining operations 
    while(!ops.empty()){ 
        int val2 = numbers.top(); 
        numbers.pop(); 

        int val1 = numbers.top(); 
        numbers.pop(); 

        char op = ops.top(); 
        ops.pop(); 

        numbers.push(maths(val1, val2, op)); 
    } 

    // Top of 'numbers' contains result, return
    return numbers.top(); 
} 

int main() { 
    cout << evaluate("10 + 10 * 10") << "\n"; 
    cout << evaluate("3 + 4 * 2 + ( 23 - 5 )") << "\n"; 
    cout << evaluate("100 * ( 2 + 12 )") << "\n"; 
    cout << evaluate("100 * ( 5 + 8 ) / 7") << "\n"; 
    return 0; 
}  

Answer 1

Учтите, что постфиксное выражение однозначно показывает порядок оценки. Например, инфиксное выражение a+b*c становится abc*+, а (a+b)*c становится ab+c*.

Если вы будете следовать оценке выражения вашего кода, вы увидите, что порядок оценки может быть представлен выражением postfix.

Вы можете изменить свой код так, чтобы он выводил постфиксное выражение одновременно с его оценкой. Основная идея заключается в том, что всякий раз, когда вы нажимаете операнд (число), вы также добавляете его в выражение postfix. И всякий раз, когда вы выполняете операцию, вы добавляете оператор к выражению постфикса. Скобки, конечно же, никогда не добавляются к постфиксу.

Итак, когда вы оцениваете (a+b)*c, вы делаете следующее:

1. Нажмите '(' на стек операторов.
2. Вставьте «a» в стек операндов и добавьте «a» к своему выражению постфикса.
3. Нажмите '+' на стек операторов.
4. Вставьте 'b' в стек операндов и добавьте 'b' к своему выражению постфикса.
5. Вы встречаете ')'. Извлеките «+» из стека операторов и добавьте к своему выражению постфикса. Извлеките «a» и «b» из стека операндов, выполните операцию и отправьте результат обратно в стек операторов.
6. Нажмите '*' в стеке операторов.
7. Нажмите 'c' в стеке операндов и добавьте к своему выражению постфикса.
8. Ты в конце выражения. Вытяните '*' из стека операторов, добавьте к выражению постфикса, вытолкните операнды и оцените.

Вы сможете легко вносить эти изменения в свой код. Каждый раз, когда вы звоните numbers.push(), также добавляйте номер к выражению вашего постфикса. Всякий раз, когда вы вызываете ops.pop(), чтобы удалить оператор (не '('), добавьте оператор popped к вашему выражению postfix. Когда вы закончите оценку, выведите выражение postfix.