C++

Forum

 
convert infix to postfix

m1m6 (37)
i have problem in convert infix to postfix

some expression evaluate it correctly

and other no

ex:
c*(a+b)

evaluate it correctly

but
A*(B*C+D)+E
doesn't evaluate correctly

and there is another problem in finding result

my code

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
// convert.h
const char SIZE=100;

class stack
{
public:
        stack();
        bool isempty()const;
        bool isfull()const;
        void push(char num);
        void pop(char &elm);
        void cntres();
        int topnum;
        void print();
        void result(stack &post);
private:
        char data[SIZE];
        int top;
};

// convert.cpp
#include<iostream>
#include"convert.h"
#include<cstddef>
#include<cstring>

using namespace std;

stack::stack()
{
        top=-1;
        topnum=top;
}

bool stack::isempty()const
{
        return top==-1;

}

bool stack::isfull()const
{
        return top==SIZE-1;
}

void stack::push(char elm)
{
if(isfull())
        cout<<"Cannot Add New Item , No Free Space ."<<endl;
else
        {
                top++;
                data[top]=elm;
                topnum=top;
        }

}
void stack::pop(char &elm)
{
        if(isempty())
                cout<<"There's No Data ."<<endl;
        else
        {
                topnum=top;
                elm=data[top];
                top--;
                
        }
}


void stack::print()
{       int i;
        cout<<"PostFix Formula : ";
        for(i=0;i<=top;i++)
        cout<<data[i];
}

void stack::result(stack &post)
{
        int i;
        int a,b,c;
        char oper;
        int res=0;
        int loop=strlen(post.data);
        for(i=0;i<=loop;i++)
{
        if(post.data[i]=='+'||post.data[i]=='-'||post.data[i]=='*'||post.data[i]=='/')
        {
                pop(oper);
                a=oper-48;
                pop(oper);
                b=oper-48;
                if (post.data[i]=='+')
                        c=a+b;
                else if (post.data[i]=='-')
                        c=a-b;
                else if (post.data[i]=='*')
                        c=a*b;
                else c=a/b;

                oper=c+48;
                push(oper);

        }
        push(post.data[i]);

}
pop(oper);
res=oper-48;
cout<<res<<endl;

}

// main
#include<iostream>
#include"convert.h"
#include<cstring>

using namespace std;

int main()
{
        stack op;
        stack post;
        stack res;
        char infex[SIZE];
        cout<<"Please Enter Infex Formula :";
        cin.get(infex,SIZE);
        char OpValue;
        char ch;
        int lenght;
        lenght=strlen(infex);
        for(int i=0;i<lenght;i++)
        {
                if(infex[i]=='+'||infex[i]=='-'||infex[i]=='*'||infex[i]=='/'||infex[i]=='('||infex[i]==')')
                {
                        if(infex[i]=='*'||infex[i]=='/'||infex[i]=='(')
                                op.push(infex[i]);
                        else if(infex[i]=='+'||infex[i]=='-')
                        {
                                if(op.topnum=='*'||op.topnum=='/')
                                {
                                        op.pop(ch);
                                        OpValue=ch;
                                        while(ch!='('&& !op.isempty())
                                        {
                                                post.push(ch);
                                                op.pop(ch);

                                        }
                                        op.push(infex[i]);
                                }
                                else
                                        op.push(infex[i]);
                                }
                        else if(infex[i]==')')
                        {
                                op.pop(ch);
                                OpValue=ch;
                                while(OpValue!='(')
                                {
                                        post.push(OpValue);
                                        op.pop(ch);
                                        OpValue=ch;
                                }

                        }


                        }
                else
                        post.push(infex[i]);

                }
        while(!op.isempty())
        {
                op.pop(ch);
                OpValue=ch;
                post.push(OpValue);     
        }

        post.print();
        cout<<endl;

        cout<<"RESULT OF INFIX : ";
        res.result(post);

system("pause");
return 0;
}
m1m6 (37)
any help ?
kbw (9488)
What's in convert.h?
m1m6 (37)
class declaration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
const char SIZE=100;

class stack
{
public:
        stack();
        bool isempty()const;
        bool isfull()const;
        void push(char num);
        void pop(char &elm);
        void cntres();
        int topnum;
        void print();
        void result(stack &post);
private:
        char data[SIZE];
        int top;
};
kbw (9488)
As far as I can tell, it works. Can you list the input/output that you think is wrong?
m1m6 (37)
Please Enter Infex Formula :2*(2+2)
PostFix Formula : 222+*
RESULT OF INFIX : -48

postfix evaluate it correctly but
tha result has an error....
kbw (9488)
The conversion to postfix is correct.

Why don't you just evaluate the postfix? You seem to ignore it once you've generated it. The whole point fo converting to postfix is because the evaluation is easy.
m1m6 (37)
my proplem is here

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


this make some expression evaluated incorrectly



The conversion to postfix is correct.


not for all expression ....
m1m6 (37)
i fixed the conversion to postfix

and it work correctly for any expression

but still
the result doesn't evaluate it correctly...
m1m6 (37)
i try to make it array of integer but it seems to be more complex

look for output

1
2
3
 
Please Enter Infex Formula :(2+7)*6
PostFix Formula : 27+6*
RESULT OF INFIX : -48

proplem in finding result
in this function

void stack::result(stack &post)
m1m6 (37)
?
kbw (9488)
There was nothing wrong to the conversion to postfix, that bit was fine. It was the evaluation that was broken.

To evaluate, start with the postfix expression.
1
2
3
4
5
6
7
8
9
 
for each token:
    if it's a number,
        push it on the evaluation stack
    else
        pop two numbers off the evaluation stack
        apply the operation
        push the result

display the number on the top of the stack


So, lets take your example.
infix: 2*(2+2) = 2 * 4 = 8

postfix: 222+*

push 2
push 2
push 2

pop 2 and 2, add them and push the result, (push 4)

pop 4 and 2, multiply them, push the result, (push 8)

display top of the stack, 8
Last edited on
m1m6 (37)
fine

but all element stored as a chars

so problem in convert from char to int
kbw (9488)
You can check if the char is a digit by calling isdigit() in ctype.h. If it's not a digit, you can assume it's an operation.
m1m6 (37)
i try to debug the code 

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
 
void stack::result(stack &post)
{
   
    int a,b,c;
   
	char num;
	int res=0;
	int loop=strlen(post.data);
	for(int i=0;i<loop;i++)
	{
	if(!(post.data[i]=='+'||post.data[i]=='-'||post.data[i]=='*'||post.data[i]=='/'))
		push(post.data[i]);
	else
	{	char num;
		pop(num);
		a=num-'0';
		pop(num);
		b=num-'0';
		if(post.data[i]=='+')
			c=a+b;
		else if (post.data[i]=='-')
			c=a-b;
			else if (post.data[i]=='*')
				c=a*b;
			else  
				c=a/b;

			num=c+'0';
			push(c);

	}

	}

	
	pop(num);
	res=num-'0';
	cout<<res<<endl;
}


still problem ....
kbw (9488)
I don't understand why you're passing in a stack into the function. I've described an algorithm that starts with an postfix expression in a string, returns a single value and uses a stack within the process.

You've already done the hard part, the infix to postfix converter. Just take string output from that and pass it to the evaluator.
m1m6 (37)
ok

i do this in main

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
 
        cout<<"RESULT OF INFIX : ";
		while(!post.isempty())
		{
			post.pop(out);
			if(out=='+'||out=='-'||out=='*'||out=='/')
			{
				char num;
				int a,b,c;
				res.pop(num);
					a=num-'0';
				res.pop(num);
				b=num-'0';

				switch(out)
				{
				case '+':
					c=a+b;
					break;
				case '-':
					c=a-b;
					break;
				case '*':
					c=a*b;
					break;
				case '/':
					c=a/b;
					break;


			}
				res.push(c);
			}
			else res.push(out);
		}

		char c;
		res.pop(out);
		c=char(out);
		cout<<c<<endl;



but couldn't find it

pls help me

this is a project
and this the last day ....
kbw (9488)
We seem to have some kind of disconnect. This is what I had in mind, but it's incomplete:
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
 
int evaluate(const std::string &postfix)
{
    for (size_t i = 0; i != postfix.size(); ++i)
    {
        if (isdigit(postfix[i]))
        {
            working_stack.push(postfix[i]);
        }
        else
        {
             int result = 0;

             int op2 = working_stack.top() - '0';
             working_stack.pop();

             int op1 = working_stack.top() - '0';
             working_stack.pop();

             switch (postfix[i])
             {
             case '+':
                 result = op1 + op2;
                 break;
             }

             working_stack.push(char(result + '0'));
        }
    }

    return working_stack.top() - '0';
}
m1m6 (37)
how i could use this function
?
i declare an array of char
kbw (9488)
You write out the postfix expression, with .print, just make it write to a general stream instead of stdout.

For example:
1
2
3
4
5
 
void stack::print(std::ostream &os)
{
    for (int i=0; i <= top; ++i)
        os << data[i];
}


Then you can print to an in-memory stream and convert that to a string:
1
2
3
4
5
6
 
    std::ostringstream os; // in-memory stream
    post.print(os); // write the stack content to the stream
    std::string postfix = os.str(); // save the stream into a string
    int value = evaluate(postfix);  // evaluate the postfix expression
    std::cout << "postfix expression: " << postfix << std::endl;
    std::cout << "value: " << value << std::endl;

Topic archived. No new replies allowed.