Problem description:
source: https://uva.onlinejudge.org/external/7/727.html
Write a program that changes an infix expression to a postfix expression according to the following specifications.
Input condition:
source: https://uva.onlinejudge.org/external/7/727.html
Write a program that changes an infix expression to a postfix expression according to the following specifications.
Input condition:
- The infix expression to be converted is in the input file in the format of one character per line, with a maximum of 50 lines in the file. For example, (3+2)*5 would be in the form: ( 3 + 2 ) * 5
- The input starts with an integer on a line by itself indicating the number of test cases. Several infix expressions follows, preceded by a blank line.
- The program will only be designed to handle the binary operators +, -, *, /.
- The operands will be one digit numerals.
- The operators * and / have the highest priority. The operators + and - have the lowest priority. Operators at the same precedence level associate from left to right. Parentheses act as grouping symbols that over-ride the operator priorities.
- Each testcase will be an expression with valid syntax
Expected uotput:
The output file will have each postfix expression all on one line. Print a blank line between different
expressions.
Sample Input
1
(
3
+
2
)
*
5
Sample Output
32+5*
Solution:
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cctype> #include <cstdio> #include<stack> #include<algorithm> using namespace std; int main() { int t, j, i, len,k, length; char expr[100]; char ch[5]; scanf("%d\n",&t); for(j=1;j<=t;j++) { stack<char> expstack; expstack.push('('); k=0; while(gets(ch)) { len=strlen(ch); if (len==0) break ; else expr[k++]=ch[0]; } expr[k++]=')'; length=k; if(j>1) printf("\n"); for(i=0;i<length;i++) { if(expr[i]=='('|| expr[i]=='+' || expr[i]=='-' || expr[i]=='*' || expr[i]=='/') { if((expr[i]=='+' || expr[i]=='-') && (expstack.top()=='*' || expstack.top()=='/' || expstack.top()=='+' || expstack.top()=='-')) { while(expstack.top()=='*' || expstack.top()=='/' || expstack.top()=='+' || expstack.top()=='-') { printf("%c",expstack.top()); expstack.pop(); } expstack.push(expr[i]); } else if((expr[i]=='*' || expr[i]=='/') &&(expstack.top()=='*' || expstack.top()=='/')) { printf("%c",expstack.top()); expstack.pop(); expstack.push(expr[i]); } else expstack.push(expr[i]); } else if(expr[i]==')') { while(expstack.top()!='(') { printf("%c",expstack.top()); expstack.pop(); } expstack.pop(); } else printf("%c",expr[i]); } while(!expstack.empty()) { printf("%c",expstack.top()); expstack.pop(); } printf("\n"); } return 0; }
No comments:
Post a Comment
Write your comment - Share Knowledge and Experience