structured-programming/finalproject.cpp at main · vexra/structured-programming · 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
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
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

std::vector<std::string> convertToInfixArray(std::string str) {
    std::vector<std::string> res;
    std::string tmp;

    for (size_t i = 0; i < str.size(); ) {
        tmp = "";

        if (isdigit(str[i])) {
            while(isdigit(str[i])) {
                tmp.push_back(str[i++]);
            }
            res.push_back(tmp);
        }

        else if (str[i] == '-') {
            tmp.push_back(str[i++]);

            if (i == 1 || (str[i-2] != ')' && !isdigit(str[i-2]))) {
                while(isdigit(str[i])) {
                    tmp.push_back(str[i++]);
                }
            }

            res.push_back(tmp);
        }


        else if (str[i] == ' ') ++i;

        else {
            tmp = str[i++];
            res.push_back(tmp);
        }

    }

    return res;
}

bool isOperator(std::string op) {
    if (op == "+" || op == "-" || op == "*" || op == "/") return true;
    return false;
}

int getPrecedence(std::string op) {
    if (op == "*" || op == "/") return 2;
    else if (op == "+" || op == "-") return 1;
    return 0;
}


std::vector<std::string> convertToPostfix(std::vector<std::string> Q) {
    std::stack<string> S;
    std::vector<string> P;

    for (size_t i = 0; i < Q.size(); ++i) {
        if (isdigit(Q[i][0]) || Q[i][0] == '-') {
            P.push_back(Q[i]);
        }

        if (Q[i] == "(") {
            S.push(Q[i]);
        }

        if (Q[i] == ")") {
            while(!S.empty() && S.top() != "(") {
              P.push_back(S.top());
              S.pop();
            }
            S.pop();
        }

        if (isOperator(Q[i])) {
            if (S.empty() || S.top() == "(") {
            	S.push(Q[i]);
            }

            else {
            	while(!S.empty() && S.top() != "(" && getPrecedence(Q[i]) <= getPrecedence(S.top())) {
            	    P.push_back(S.top());
            	    S.pop();
            	}
            }
        }
    }

    while(!S.empty()) {
        P.push_back(S.top());
        S.pop();
    }

    return P;
}

int main()
{
    std::string text = "-5*6 + 2 - 12 / 4";
    std::vector<std::string> infixArray = convertToInfixArray(text);
    // std::vector<std::string> infixArray = {"5", "*", "(", "6", "-", "2", ")", "-", "12", "/", "-4"};
    std::vector<std::string> postfixArray = convertToPostfix(infixArray);

    // Print the postfix array
    for (const auto& token : postfixArray) {
        std::cout << token << std::endl;
    }
}