Infix to Prefix

rem45acp (48)
Hello,

I've made an attempt at converting infix expressions to prefix form using the shunting yard algorithm:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

I have adopted the algorithm to start the main loop at the end of the string and work backwards, as well as reverse the string at the end (like they stated) to accommodate going to prefix instead of postfix. This works fine for expressions not containing parenthesis, but on line 44 I get a dereference error (trying to access the top value of the stack when there is no top value). Can't figure out how to modify the case for the close parenthesis:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
void infixToPrefix(std::string &expr)
{
    //Use temp as a working string.
    std::string temp = expr;
    //Clear the input/output string and use it as the output queue.
    expr.clear();

    std::stack <char> opStack;

    //Because of prefix, start at the end of the string and work down.
    for (int i = temp.length() - 1; i >= 0; --i)
    {
        const char cur = temp[i]; //avoid tonnage of dereferences.

        switch (cur)
        {
        case '*':
        case '/':
        case '+':
        case '-':

            //All this works fine.
            while (!opStack.empty() && (precedence(opStack.top()) <= precedence(cur)))
            {
                expr.push_back(opStack.top());

                opStack.pop();
            }

            opStack.push(cur);

            break;

        case '(': //We are on an opening parenthesis.

            //Push it on to the opStack as well;
            opStack.push(cur); 
            break;

        case ')': //We are on a closing parenthesis.

            //Start removing operators from the opStack until the open
            //parenthesis is found.
            while (opStack.top() != '(')
            {
                //Push the operator from the top of the stack into the expression.
                expr.push_back(opStack.top());

                //Pop that operator from the stack.
                opStack.pop();
            } //end while


            opStack.pop();
            break;

        default:

            expr.push_back(cur);

            break;
        }
    }

    while (!opStack.empty())
    {
        expr.push_back(opStack.top());

        opStack.pop();
    }

    //reverse the string
    expr = std::string(expr.rbegin(), expr.rend());
}

int main(int argc, char *argv[])
{
    std::string expr = "(a+b)*c";
    std::cout << expr << std::endl;

    infixToPrefix(expr);
    
    std::cout << expr;

    return 0;
}


I'm so close!
rem45acp (48)
Well I ended up changing line 23 to:

while (!opStack.empty() && opStack.top() != '(' && (precedence(opStack.top()) <= precedence(cur)))

and the case ')': statement to:

1
2
3
4
5
6
7
8
9
 
  
while (!opStack.empty() && opStack.top() != '(')
{
    expr.push_back(opStack.top());
    opStack.pop();
} //end while

if (!opStack.empty())
    opStack.pop();


and inserted into the final while loop for removing the trailing operators in the stack:
(this avoids putting the parenthesis into the expr)
1
2
3
4
5
 
if (opStack.top() == '(')
{
    opStack.pop();
    continue;
}


However I fell like checking for the opening parenthesis in the final while loop a little bit of a hack. I'm still open to suggestions.
Topic archived. No new replies allowed.