Infix to Postfix Algorithm

porecelainpotato (1)
Write your question here.
I am trying to write an algorithm using stacks that converts an infix expression into a postfix expression(ex (6 + 13) * 2 – (5 + 1)/3 -> 613 + 2*5 1 +3 / -

My current output looks like 613+251+3/*
Please help! Thank you
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
 
//
//
//
//
#include <iostream>
#include <stack>
#include <string>

using namespace std;

//Function to return precedence of operators
int prec(char c)
{
    int temp = 0;
    if(c == '+' || c == '-')
        temp = 1;
    else if(c == '*' || c == '/')
        temp = 2;
    return temp;
}


bool isOperator(char input)
{
    if(input == '+' || input == '-' || input == '*' || input == '/')
        return true;
    return false;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
    stack<char> st; //stack for operators
    string ns; //converted string
    for(int i = 0; i < s.length(); i++)
    {
        // If the scanned character is an operand, add it to output string.
        if(isdigit(s[i]))
            ns+=s[i];
        // If the scanned character is an ‘(‘, push it to the stack.
        else if(s[i] == '(')
            st.push('(');
        //If an operator is scanned
        else if(isOperator(s[i])){
            bool found = false;
            do{
                if(st.empty())
                {
                    st.push(s[i]);
         
                    found = true;
                }
                else if(st.top() == '(')
                {
                    st.push(s[i]);
                
                    found = true;
                }
                else if(prec(s[i]) >= prec(st.top())){
                    st.push(s[i]);
            
                    found = true;
                }
                else{
                    ns+=st.top();
                    st.pop();
                }
            }while(!found);
        }
           
        // If the scanned character is an ‘)’, pop and to output string from the stack
        // until an ‘(‘ is encountered. Pop and discard '('
        else if(s[i] == ')'){
            while(st.top() != '(' && !isdigit(s[i])){
                ns += st.top();
                st.pop();
            }
            if(st.top() == '('){
                st.pop();
            }
        }
    }
    //Pop all the remaining elements from the stacl
    while(!st.empty())
           {
                 ns += st.top();
                 st.pop();
           }
    cout << ns << endl;
}

int main()
{
    string exp = "(6 + 13) * 2 – (5 + 1)/3";
    infixToPostfix(exp);
    return 0;
}
Last edited on
dutch (2548)
I haven't looked at your code, but one obvious problem is that you are using a unicode "en dash" (U+2013) instead of a regular dash in your input.
dhayden (5799)
Replace
ns += st.top();
with
1
2
3
 
ns += ' ';
ns += st.top();
ns ++ ' ';

in all 3 places.
Topic archived. No new replies allowed.