C++

Forum

 
 
Postfix to Infix Conversion with multiple digit integers

alenko92 (5)
Hello, I'm currently working in a c++ program that computes postfix expressions and then converts the postfix expression into an infix expression. I've been doing some research and got the code to work when the integer is only one digit. Can someone help me out modifying so it would accept multiple digit inputs?

Thank you. Appreciate your help

This is the function that's giving me trouble:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
string getInfix(string expression) { 
    stack<string> s; 
    for (int i=0; i<expression.length(); i++) { 
        if(expression[i] == ' ' || expression[i] == ',' || expression[i] == '\'' || expression[i] == '\"') 
		continue; 
        else if (!isOperator(expression[i])) { 
            string operand(1, expression[i]); 
            s.push(operand); 
        }
        else { 
            string operand1 = s.top(); 
            s.pop();
            string operand2 = s.top();
            s.pop();
            s.push("(" + operand2 + expression[i] + operand1 + ")");
        }
    }
    return s.top();
}
Last edited on
dhayden (5799)
Well, line 7 creates a string called operand that is 1 character long. Is that the problem?

It's hard to tell what's happening here without the rest of the code. For your description it sounds like expression is a postfix expression. But why would it contain a comma, single quote or double quote?

Can you post a program that compiles and demonstrates the problem?
alenko92 (5)
Sure thing, here is my full 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
 
#include <iostream>
#include <stack>
#include <string>

using namespace std;

// Function to verify if character is a number
bool isNumber(char c) {
	if(c >= '0' && c <= '9') 
    return true;
	return false;
}
// Function to verify if a character is an operator
bool isOperator(char c) {
    if(c == '+' || c == '-' || c == '*' || c == '/')
    return true;
    return false;
}
// Push function to push two digit integers
void push(int symbol){
    int stack[100];
    int top;
    if (stack[top] >= 0 && stack[top] <= 9) {
        stack[top] *= 10;
        stack[top] += symbol;
    }
    else {
        stack[++top]=symbol;
    }
}
// Function to perform an operation
int PerformOperation(char operation, int operand1, int operand2) {
    if(operation == '+') return operand1 +operand2;
	else if(operation == '-') return operand1 - operand2;
	else if(operation == '*') return operand1 * operand2;
	else if(operation == '/') return operand1 / operand2;
    else cout << "Unexpected Error" << endl;
    return -1; 
}
// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression) {
    stack<int> S;
    for(int i = 0; i<expression.length(); i++) {
		// Scan characters, if character is a delimitter, continue
		if(expression[i] == ' ' || expression[i] == ',' || expression[i] == '\'' || expression[i] == '\"') 
		continue; 
        // If the character is an operator, pop two elements from stack, 
        // perform operation and pushback the result
		else if(isOperator(expression[i])) {
            int operand2 = S.top(); S.pop();
			int operand1 = S.top(); S.pop();
			int result = PerformOperation(expression[i], operand1, operand2);
			S.push(result);
        }
		else if(isNumber(expression[i])){
            // Take the operand from the string and increment i as long as input is a number 
			int operand = 0; 
			while(i<expression.length() && isNumber(expression[i])) {
                operand = (operand*10) + (expression[i] - '0'); 
                i++;
            }
            i--;
            S.push(operand);
        }
    }
    return S.top();
}
// Convert the postfix Expression to an infix Expression
string getInfix(string expression) { 
    stack<string> s; 
    for (int i=0; i<expression.length(); i++) { 
        if(expression[i] == ' ' || expression[i] == ',' || expression[i] == '\'' || expression[i] == '\"') 
		continue; 
        else if (isNumber(expression[i])) { 
            string operand(1, expression[i]); 
            s.push(operand); 
        }
        else { 
            string operand1 = s.top(); 
            s.pop();
            string operand2 = s.top();
            s.pop();
            s.push("(" + operand2 + expression[i] + operand1 + ")");
        }
    }
    return s.top(); 
}

int main(){
	string expression = ("'2','1','+','3','*'");
	int result = EvaluatePostfix(expression);
	string expression2= ("\"4\",\"13\",\"5\",\"/\",\"+\"");
	int result2 = EvaluatePostfix(expression2);
    string expression3= ("2 1 + 3 *");
    int result3 = EvaluatePostfix(expression3);
    string expression4 = ("4 13 5 / +");
    int result4 = EvaluatePostfix(expression4);
    
	cout << "Input: {" << expression << "}; Output: " << result << " Explanation: " 
    << getInfix(expression) <<endl;
	cout << "Input: {" << expression2 << "}; Output: " << result2 << " Explanation: " 
    << getInfix(expression2) << endl;
}
alenko92 (5)
And here is the output:

Input: {'2','1','+','3','*'}; Output: 9 Explanation: ((2+1)*3)
Input: {"4","13","5","/","+"}; Output: 6 Explanation: (1+(3/5))

[Done] exited with code=0 in 1.927 seconds

As you can see from the second part, the 13 is identified as two separate characters because of how I have the infix function. The output should be (4+(13/5))
dhayden (5799)
function push() is unused. That's a good thing since the local variables are uninitialized.

The output from the second part (6) is correct. It's the explanation that's wrong. And that's because of the very first thing I said:
Well, line 7 [in your original post] creates a string called operand that is 1 character long. Is that the problem?


The fundamental problem here is that you have two chunks of code that parse the expression. You should write a single function to do this instead. The function returns a token string and the type of the token. Once that's written, getInfix() and EvaluatePostfix() become very simple:
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
 
#include <iostream>
#include <stack>
#include <string>
#include <cstring>

using namespace std;

// Function to verify if character is a number
bool
isNumber(char c)
{
    if (c >= '0' && c <= '9')
	return true;
    return false;
}

// Function to verify if a character is an operator
bool
isOperator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/')
	return true;
    return false;
}

// Function to perform an operation
int
PerformOperation(char operation, int operand1, int operand2)
{
    if (operation == '+')
	return operand1 + operand2;
    else if (operation == '-')
	return operand1 - operand2;
    else if (operation == '*')
	return operand1 * operand2;
    else if (operation == '/')
	return operand1 / operand2;
    else
	cout << "Unexpected Error" << endl;
    return -1;
}

enum TokenType {Number, Operator};

// Read a token from "line", starting at "pos".  On success, return
// true, update pos, and set the token and its type in "token" and
// "type".  On failure, return false.
bool
nextToken(const string &line, size_t &pos, string &token, TokenType &type)
{
    
    // Skip delimiters and return if you hit end of string.
    // Notice the trick with strchr to see if the character is one of a set.
    while (pos < line.size() && strchr(" ,\'\"", line[pos])) {
	++pos;
    }
    if (pos == line.size()) return false;

    token.clear();

    if (isOperator(line[pos])) {
	type = Operator;
	token = line[pos++];
	return true;
    }

    // It must be a number. Read it and return it.
    while (pos < line.size() && isNumber(line[pos])) {
	token += line[pos++];
    }
    type = Number;
    return true;
}

// Function to evaluate Postfix expression and return output
int
EvaluatePostfix(string expression)
{
    stack < int >S;
    string token;
    enum TokenType type;
    size_t pos=0;
    while (nextToken(expression, pos, token, type)) {
	switch (type) {
	case Operator:
	    {
		// pop two elements from stack, 
		// perform operation and pushback the result
		int operand2 = S.top();
		S.pop();
		int operand1 = S.top();
		S.pop();
		int result = PerformOperation(token[0], operand1, operand2);
		S.push(result);
		break;
	    }
	case Number:
	    {
		// Convert the token to a number and push it on the stack
		int operand = atoi(token.c_str());
		S.push(operand);
		break;
	    }
	}
    }
    return S.top();
}

// Convert the postfix Expression to an infix Expression
string
getInfix(string expression)
{
    stack < string > s;
    string token;
    enum TokenType type;
    size_t pos=0;

    while (nextToken(expression, pos, token, type)) {
	switch (type) {
	case Operator:
	    {
		string operand2 = s.top();
		s.pop();
		string operand1 = s.top();
		s.pop();
		s.push("(" + operand1 + token + operand2 + ")");
		break;
	    }
	case Number:
	    s.push(token);
	    break;
	}
    }
    return s.top();
}

int
main()
{
    string expression = ("'2','1','+','3','*'");
    int result = EvaluatePostfix(expression);
    string expression2 = ("\"4\",\"13\",\"5\",\"/\",\"+\"");
    int result2 = EvaluatePostfix(expression2);
    string expression3 = ("2 1 + 3 *");
    int result3 = EvaluatePostfix(expression3);
    string expression4 = ("4 13 5 / +");
    int result4 = EvaluatePostfix(expression4);

    cout << "Input: {" << expression << "}; Output: " << result << " Explanation: "
	<< getInfix(expression) << endl;
    cout << "Input: {" << expression2 << "}; Output: " << result2 << " Explanation: "
	<< getInfix(expression2) << endl;
}

alenko92 (5)
Thanks, I'll spend some time to understand the logic behind TokenType and enum, thank you so much for your help.
MikeStgt (466)
Nice. It seems the brackets in the infix notation are not dependent on operator hierarchies.
Exchanging the operators of the first example
Input: {'2','1','+','3','*'}; Output: 9 Explanation: ((2+1)*3)

results in
Input: {'2','1','*','3','+'}; Output: 5 Explanation: ((2*1)+3)

which would not need any brackets at all. Same for the second example:
Input: {"4","13","5","/","+"}; Output: 6 Explanation: (4+(13/5))
Topic archived. No new replies allowed.