Infix to Postfix Conversion With Stack

LunyJake (3)
My professor gave us pseudocode as a guide but the parenthesis always end up in the postfix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
while there are more characters in the input
{
    Read next symbol ch in the given infix expression.
    If ch is an operand put it on the output.
    If ch is an operator i.e.* , /, +, -, or (
    {
        If stack is empty 
             push ch onto stack;
        Else 
            check the item op at the top of the stack;
            while (more items in the stack && priority(ch) <= priority (op) )
            {
                  pop op and append it to the output, provided it is not an open parenthesis
                  op = top element of stack
             }
             push ch onto stack
     }
     If ch is right parenthesis ‘)’
          Pop items from stack until left parenthesis reached
          Pop left parenthesis and discard both left and right parenthesis
} /* now no more characters in the infix expression*/
Pop remaining items in the stack to the output.


Thats the pseudocode he gave us and this is 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
 
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int priority(char a);
void inputString(string& a);
void removeEmbeddedSpaces(string& a, string& b);
void convertInfixToPostfix(string& a, string& b, stack<char>& c);

int main(){
	string infix, noSpcInfix, postFix;
	stack<char> postFixStk;
	
	inputString(infix);
	removeEmbeddedSpaces(infix, noSpcInfix);
	convertInfixToPostfix(noSpcInfix, postFix, postFixStk);
	
	return 0;
}

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

void inputString(string& a){
	cout << "Enter an infix expression: ";
	getline(cin, a);
}

void removeEmbeddedSpaces(string& a, string& b){
	cout << "After removing embedded spaces, infix expressions becomes: ";
	for(int i = 0; i < a.length(); i++){
		if(a[i] != ' '){
			b.push_back(a[i]);	
		}
	}
	cout << b;
}

void convertInfixToPostfix(string& a, string& b, stack<char>& c){
	cout << "\n\n\nThe corresponding postfix is: ";
	for(int i = 0; i < a.length(); i++){
		if(a[i] != '*' && a[i] != '/' && a[i] != '+' && a[i] != '-' && a[i] != '('){
			b.push_back(a[i]);
		}
		else if(a[i] == '*' || a[i] == '/' || a[i] == '+' || a[i] == '-' || a[i] == '('){
			if(c.empty()){
				c.push(a[i]);
			}
			else{
				while(!c.empty() && c.top() != '(' && priority(c.top()) <= priority(a[i])){
					b.push_back(c.top());
					c.pop();
				}
				c.push(a[i]);
		    }
		}
		else if(a[i] == ')'){
			while(c.top() != '('){
				b.push_back(c.top());
				c.pop();
			}
			if(c.top() == '('){
				c.pop();
			}
			c.pop();
		}
	}

	while(!c.empty()){
		b.push_back(c.top());
		c.pop();
    }

	cout << b;
}


Any help would be appreciated! I'm new to stacks so I don't know if it is a stack problem or if I just did something else wrong.
Last edited on
seeplus (6592)
The main issue is L52. If a[i] is '(', L67 is not executed!

Try:

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
 
#include <iostream>
#include <stack>
#include <string>

int priority(char a);
std::string inputString();
std::string removeEmbeddedSpaces(const std::string& a);
std::string convertInfixToPostfix(const std::string& a);

int main() {
	const auto infix {inputString()};

	std::cout << "\nThe corresponding postfix is : " << convertInfixToPostfix(infix) << '\n';
}

int priority(char a) {
	int pty = 0;

	if (a == '*' || a == '/')
		pty = 1;
	else if (a == '+' || a == '-')
		pty = 2;

	return pty;
}

std::string inputString() {
	std::string a;

	std::cout << "Enter an infix expression: ";
	std::getline(std::cin, a);
	return removeEmbeddedSpaces(a);
}

std::string removeEmbeddedSpaces(const std::string& a) {
	std::string b;

	//cout << "After removing embedded spaces, infix expressions becomes: ";
	for (int i = 0; i < a.length(); i++)
		if (a[i] != ' ')
			b.push_back(a[i]);

	return b;
}

std::string convertInfixToPostfix(const std::string& a) {
	std::stack<char> c;
	std::string b;

	for (int i = 0; i < a.length(); i++) {
		if (a[i] != '*' && a[i] != '/' && a[i] != '+' && a[i] != '-' && a[i] != '(' && a[i] != ')')
			b.push_back(a[i]);
		else
			if (a[i] == '*' || a[i] == '/' || a[i] == '+' || a[i] == '-' || a[i] == '(') {
				if (c.empty())
					c.push(a[i]);
				else {
					while (!c.empty() && c.top() != '(' && priority(c.top()) <= priority(a[i])) {
						b.push_back(c.top());
						c.pop();
					}

					c.push(a[i]);
				}
			} else
				if (a[i] == ')') {
					while (c.top() != '(') {
						b.push_back(c.top());
						c.pop();
					}

					c.pop();
				}
	}

	while (!c.empty()) {
		b.push_back(c.top());
		c.pop();
	}

	return b;
}



Enter an infix expression: 1*(2+3)

The corresponding postfix is : 123+*

Last edited on
LunyJake (3)
Wow, I feel so dumb. Thank you so much @seeplus!
Topic archived. No new replies allowed.