UVA solution 727 Equation

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:

  1.  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 
  2.  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. 
  3.  The program will only be designed to handle the binary operators +, -, *, /. 
  4.  The operands will be one digit numerals. 
  5. 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. 
  6.  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 

(
 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;
}
image

No comments:

Post a Comment

Write your comment - Share Knowledge and Experience