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