0

作为大学项目的一部分,我写了一个关于 Dijkstra 的 Shutting Yard Algorithm 的尝试。一切都按预期工作,但我还需要展示操作员在处理后是如何排序的,我不知道该怎么做,我相信最好的方法是队列?有谁知道如何做到这一点?我的代码:

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

1 回答 1

0

考虑一个后缀表达式明确地显示评估顺序。例如,中缀表达式a+b*c变为abc*+,然后(a+b)*c变为ab+c*

如果您遵循代码的表达式评估,您将看到评估顺序可以由后缀表达式表示。

您可以修改代码以在评估的同时输出后缀表达式。基本思想是,每当你推送一个操作数(一个数字)时,你也会将它附加到你的后缀表达式中。并且无论何时执行操作,您都将操作符附加到后缀表达式。当然,括号永远不会添加到后缀中。

因此,当您评估 时(a+b)*c,请执行以下操作:

  1. 将 '(' 推入运算符堆栈。
  2. 将“a”压入操作数堆栈,并将“a”附加到您的后缀表达式。
  3. 将“+”压入运算符堆栈。
  4. 将“b”推入操作数堆栈,并将“b”附加到您的后缀表达式。
  5. 你遇到')'。从运算符堆栈中弹出“+”并附加到您的后缀表达式。从操作数堆栈中弹出“a”和“b”,执行操作,并将结果推回操作数堆栈。
  6. 将“*”推送到运算符堆栈。
  7. 将“c”推送到操作数堆栈,并附加到您的后缀表达式。
  8. 你在表达式的末尾。从运算符堆栈中弹出“*”,附加到后缀表达式,弹出操作数并计算。

您应该能够在代码中轻松地进行这些更改。每当您调用numbers.push()时,还要将数字附加到您的后缀表达式中。每当您调用ops.pop()删除运算符(不是“(”)时,将弹出的运算符附加到您的后缀表达式。完成评估后,输出后缀表达式。

于 2019-06-11T17:55:23.780 回答