Created
January 11, 2019 08:46
-
-
Save lokesh541/2236645604160bc2e857e3266f4e241e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> //this will inlcude all the header files commonly used in programming contets doesn't work out side of contests | |
| using namespace std; | |
| #define rep(i, a, b) for (int i = a; i < (b); ++i) | |
| #define trav(a, x) for (auto &a : x) | |
| #define all(x) x.begin(), x.end() | |
| #define sz(x) (int)(x).size() | |
| typedef long long ll; //just for convinence you don't have to type long long every time | |
| typedef pair<int, int> pii; | |
| typedef vector<int> vi; | |
| typedef stack<char> si; | |
| int main() | |
| { | |
| //code to make cin and cout faster | |
| cin.sync_with_stdio(0); | |
| cin.tie(0); | |
| cin.exceptions(cin.failbit); | |
| int t; | |
| si ops; | |
| string s, p = ""; | |
| //using map for storing precdences | |
| map<char, int> pre; | |
| pre['+'] = 1; | |
| pre['-'] = 2; | |
| pre['*'] = 3; | |
| pre['/'] = 4; | |
| pre['^'] = 5; | |
| cin >> t; | |
| while (t--) | |
| { | |
| cin >> s; | |
| // cout<<sz(s)<<endl; | |
| for (int i = 0; i < sz(s); i++) | |
| { | |
| if (isalpha(s[i])) | |
| { | |
| p += s[i]; // if it is a character add it to the output | |
| } | |
| if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '^') | |
| { | |
| if (!ops.empty() && ops.top() != '(') | |
| { | |
| while (pre[ops.top()] >= pre[s[i]]) /* if the operator at the top of the stack has higher precedence add | |
| it to the out put and pop it from the stack*/ | |
| { | |
| p += ops.top(); | |
| ops.pop(); | |
| } | |
| } | |
| ops.push(s[i]); // push the operator on to the stack | |
| } | |
| if (s[i] == '(') | |
| { | |
| ops.push(s[i]); //if the token is '(' push it into the stack | |
| } | |
| if (s[i] == ')') //if the token is ')' add all the operators to the output until you encounter '(' | |
| { | |
| while (!ops.empty()) | |
| { | |
| if (ops.top() == '(') | |
| { | |
| ops.pop(); | |
| break; | |
| } | |
| else | |
| { | |
| p += ops.top(); | |
| ops.pop(); | |
| } | |
| } | |
| } | |
| } | |
| cout << p << endl; | |
| p = ""; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment