C++

Forum

 
 
Problem with converting from infix to postfix notation

DoABarrelRoll94 (51)
The program works fine when I input an expression without parentheses but not when I include parentheses. 

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

int prcd(char);                 //returns an int; the higher the int, the higher the precedence
int eval(int, int, char);      //evaluates expression

int main()
{
    stack<char> op;
    string infix;
    stringstream output;
    
    cout << "Enter an arithmetic expression in infix notation.\n";
    getline(cin,infix);
    
    
    for(int i = 0; i < infix.size(); i++)
    {
        if(infix[i] == '*' || infix[i] == '/' || infix[i] == '+' || infix[i] == '-')
        {
            while(!op.empty() && prcd(op.top() >= prcd(infix[i])))      //char from infix is *, /, +, or -
            {
                output << op.top();
                op.pop();
            }
            op.push(infix[i]);
        }
        else if(infix[i] == '(')                                        //char from infix is (
        {
            op.push(infix[i]);
        }
        else if(infix[i] == ')')                                        //char from infix is )
        {
            while(op.top() != '(')
            {
                output << op.top();
                op.pop();
            }
            op.pop();
        }
        else                                                            //char is an operand
        {
            output << infix[i];
        }
    }
    
    while(!op.empty())
    {
        output << op.top();
        op.pop();
    }
    
    string postfix = output.str();
    
    stack<int> result;
    int op1, op2;
    
    for(int i = 0; i < postfix.size(); i++)
    {
        if(isdigit(postfix[i]))
        {
            result.push(postfix[i]);
        }
        else
        {
            op2 = result.top() - '0';
            result.pop();
            op1 = result.top() - '0';
            result.pop();
            int value = eval(op1, op2, postfix[i]);
            result.push(value);
        }
    }
    cout << "The final result is " << result.top() << "." << endl;
    
    return 0;
}

int prcd(char e)
{
    int temp;
    
    if(e == '*' || e == '/')
    {
        temp = 2;
    }
    else if(e =='+' || e == '-')
    {
        temp = 1;
    }
    return temp;
}

int eval(int op1, int op2, char op)
{
    switch(op)
    {
        case '*': return op1 * op2;
            break;
        case '/': return op1 / op2;
            break;
        case '+': return op1 + op2;
            break;
        case '-': return op1 - op2;
            break;
        default: return 0;
    }
}
DoABarrelRoll94 (51)
The error shows up on line 38. It is a bad access error. It seems like the logic behind my code is correct. 

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

int prcd(char);                 //returns an int; the higher the int, the higher the precedence
int eval(int, int, char);      //evaluates expression

int main()
{
    stack<char> op;
    string infix;
    stringstream output;
    
    cout << "Enter an arithmetic expression in infix notation.\n";
    getline(cin,infix);
    
    
    for(int i = 0; i < infix.size(); i++)
    {
        if(infix[i] == '*' || infix[i] == '/' || infix[i] == '+' || infix[i] == '-')
        {
            while(!op.empty() && prcd(op.top() >= prcd(infix[i])))      //char from infix is *, /, +, or -
            {
                output << op.top();
                op.pop();
            }
            op.push(infix[i]);
        }
        else if(infix[i] == '(')                                        //char from infix is (
        {
            op.push(infix[i]);
        }
        else if(infix[i] == ')')                                        //char from infix is )
        {
            while(op.top() != '(')
            {
                output << op.top();
                op.pop();
            }
            op.pop();
        }
        else                                                            //char is an operand
        {
            output << infix[i];
        }
    }
    
    while(!op.empty())
    {
        output << op.top();
        op.pop();
    }
    
    cout << "Postfix expression: " << output.str() << endl;             //output the postfix string
    
    string postfix = output.str();
    
    stack<int> result;
    int op1, op2;
    
    for(int i = 0; i < postfix.size(); i++)                             //evaluate postfix expression
    {
        if(isdigit(postfix[i]))
        {
            result.push(postfix[i] - '0');
        }
        else
        {
            op2 = result.top();
            result.pop();
            op1 = result.top();
            result.pop();
            int value = eval(op1, op2, postfix[i]);
            result.push(value);
        }
    }
    cout << "The final result is " << result.top() << "." << endl;
    
    return 0;
}

int prcd(char e)
{
    int priority;
    
    if(e == '*' || e == '/')
    {
        priority = 2;
    }
    else if(e =='+' || e == '-')
    {
        priority = 1;
    }
    return priority;
}

int eval(int op1, int op2, char op)
{
    switch(op)
    {
        case '*': return op1 * op2;
            break;
        case '/': return op1 / op2;
            break;
        case '+': return op1 + op2;
            break;
        case '-': return op1 - op2;
            break;
        default: return 0;
    }
}
Last edited on
DoABarrelRoll94 (51)
I cannot find out why there is an error. I followed the algorithm correctly given by my professor so I don't know why it isn't working with parentheses.
Diedes (21)
What is the exact problem? Because when I run your code, it runs fine. for example when I enter 6546754 it returns 5.
DoABarrelRoll94 (51)
At first I thought it was just when I entered parentheses into the expression, e.g., "(3+5)*5, but it seems like the conversion from infix to postfix is also incorrect. The error when I input expression with parentheses occurs on line 38.
DoABarrelRoll94 (51)
NEVERMIND SOLVED! YEEEEAAAHHHH!!!
DoABarrelRoll94 (51)
I just changed the prcd function. I don't know why but when I was returning the int variable priority in the previous code, I was getting an error. I changed it to return the actual int and now it works. Weird. 

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <iostream>     //cin, cout
#include <sstream>      //stringstream, str()
#include <stack>        //for stack container
#include <string>       //string
#include <cctype>       //isdigit()
#include <cstdlib>      //exit()
using namespace std;

int prcd(char);                 //returns an int; the higher the int, the higher the precedence
int eval(int, int, char);      //evaluates expression

int main()
{
    stack<char> op;     //stack for operators
    string infix;
    stringstream output;
    
    cout << "Enter an arithmetic expression in infix notation.\n";
    getline(cin,infix);
    
    //CONVERTING FROM INFIX TO POSTFIX//
    
    for(int i = 0; i < infix.size(); i++)
    {
        if(infix[i] == '*' || infix[i] == '/' || infix[i] == '+' || infix[i] == '-')        //char from infix is *, /, +, or -
        {
            while(!op.empty() && prcd(op.top() >= prcd(infix[i])))      //while top of operator stack is not empty & prec is equal or greater
            {
                output << op.top();
                op.pop();
            }
            op.push(infix[i]);
        }
        else if(infix[i] == '(')                                        //char from infix is (
        {
            op.push(infix[i]);
        }
        else if(infix[i] == ')')                                        //char from infix is )
        {
            while(!op.empty() && op.top() != '(')
            {
                output << op.top();
                op.pop();
            }
            op.pop();
        }
        else if(isdigit(infix[i]))                                      //char is an number
        {
            output << infix[i];
        }
    }       //end of for loop
    
    while(!op.empty())
    {
        output << op.top();
        op.pop();
    }
    
    cout << "Postfix expression: " << output.str() << endl;             //output the postfix string
    
    string postfix = output.str();
    
    stack<int> result;
    int op1, op2;
    
    //EVALUATING POSTFIX EXPRESSION//
    
    for(int i = 0; i < postfix.size(); i++)                             //evaluate postfix expression
    {
        if(isdigit(postfix[i]))
        {
            int value = postfix[i] - '0';
            result.push(value);
        }
        else
        {
            op2 = result.top();
            result.pop();
            op1 = result.top();
            result.pop();
            int value = eval(op1, op2, postfix[i]);
            result.push(value);
        }
    }       //end of for loop
    cout << "The final result is " << result.top() << "." << endl;
    
    return 0;
}

int prcd(char e)                        //returns an int; the higher the int, the higher the precedence
{
    if(e == '*' || e == '/')
    {
        return 2;
    }
    else if(e =='+' || e == '-')
    {
        return 1;
    }
    else return 0;
}

int eval(int op1, int op2, char op)     //evaluates expression
{
    switch(op)
    {
        case '*': return op1 * op2;
            break;
        case '/':
            if(op2 == 0)
            {
                cout << "Cannot divide by 0.\n";
                exit(0);
            }
            else
            {
            return op1 / op2;
            }
            break;
        case '+': return op1 + op2;
            break;
        case '-': return op1 - op2;
            break;
        default: return 0;
    }
}
Topic archived. No new replies allowed.