DSA/InfixToPostfix.cpp at main · mdNafish1527/DSA · GitHub

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
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int priority(char ch){
    if(ch == '+' || ch == '-') return 1;
    else return 2;
}


int main(){
    string str = "(7+9)*4/8-3";
    stack<string> val;
    stack<char> opr;

    for(int i = 0 ; i < str.size() ; i++){
        if(str[i] >= '0' && str[i] <= '9'){
            val.push(to_string(str[i] - '0'));
        }
        else{
            if(opr.empty() || str[i] == '(' || opr.top() == '(') opr.push(str[i]);
            else if(str[i] == ')'){
                while(opr.top() != '('){
                    char ch = opr.top();
                    opr.pop();
                    string a = val.top();
                    val.pop();
                    string b = val.top();
                    val.pop();

                    string ans = "";
                    ans += b;
                    ans += a;
                    ans.push_back(ch);
                    val.push(ans);
                }
                opr.pop();
            }
            else if(priority(str[i]) > priority(opr.top())) opr.push(str[i]);
            else{
                while(opr.size() > 0 && priority(str[i]) <= priority(opr.top())){
                    char ch = opr.top();
                    opr.pop();
                    string a = val.top();
                    val.pop();
                    string b = val.top();
                    val.pop();

                    string ans = "";
                    ans += b;
                    ans += a;
                    ans.push_back(ch);
                    val.push(ans);
                }
                opr.push(str[i]);
            }
        }
    }


    while(opr.size() > 0){
        char ch = opr.top();
        opr.pop();
        string a = val.top();
        val.pop();
        string b = val.top();
        val.pop();

        string ans = "";
        ans += b;
        ans += a;
        ans.push_back(ch);
        val.push(ans);
    }

    cout << val.top() << endl;
    return 0;
}