[UVa] 727 - Equation

Method: Stack
Tricky case: None that comes to mind. Even though some people are saying that cases like (1+2)3 exist, they don't because my code doesn't take them into account.

Sample Input:

20

0
*
8
-
4
*
6
+
4
/
7
*
2

(
3
+
(
3
+
2
)
*
(
4
+
5
+
2
)
*
(
1
+
2
-
3
/
(
1
-
2
*
(
4
+
4
)
)
)
)
-
3
*
5

(
3
+
(
3
+
2
)
*
(
4
+
5
+
2
)
*
(
1
+
2
-
3
/
(
1
-
2
*
(
4
+
4
)
)
)
)
-
3
*
5

1
+
(
2
*
3
)
*
4

(
1
+
2
)
3

1
+
2
*
3

1
+
2
-
3

1
+
2
*
3

(
1
+
2
)
/
(
3
-
4
)

(
(
1
+
2
)
*
(
3
-
4
)
+
5
)
/
(
6
+
7
)

(
1
*
(
2
+
3
+
(
4
*
5
)
)
+
1
)

(
(
(
1
)
)
)

1

( 
1 
+ 
2 
) 
3 

(
3
/
(
2
+
5
)
+
9
*
5
-
1
/
3
)

(
)

(
3
+
2
)
*
5

(
3
+
2
)
*
5

(
3
+
2
-
4
)
*
5

(
(
3
+
2
)
-
4
)
+
9

Sample Output:

08*46*-47/2*+

332+45+2+*12+31244+*-/-*+35*-

332+45+2+*12+31244+*-/-*+35*-

123*4*+

12+3

123*+

12+3-

123*+

12+34-/

12+34-*5+67+/

123+45*+*1+

1

1

12+3

325+/95*+13/-



32+5*

32+5*

32+4-5*

32+4-9+

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

int rating[1000];

string proc(string inp)
{
    int i;
    string prnt="";
    stack <char> stk;

    for (i=0 ; i<inp.size() ; i++)
    {



        if ( inp[i] == '(' ) { stk.push(inp[i]); }
        if ( inp[i] == ')' )
        {
            while (stk.top()!='(')
            {
                char ch = stk.top();
                stk.pop();
                prnt += ch;
            }
            stk.pop();

        }

        if ( inp[i]=='/' || inp[i]=='*' || inp[i]=='+' || inp[i]=='-' )
        {
            if (stk.empty() || stk.top()=='(')
            {
                stk.push(inp[i]);
            } else
            {
                while (!stk.empty() && rating[ inp[i] ] <= rating[ stk.top() ])
                {
                    char ch = stk.top();
                    stk.pop();
                    prnt += ch;
                }
                stk.push( inp[i] );
            }
        }


        if (inp[i]>='0' && inp[i]<='9')
        {
            prnt += inp[i];
        }
    }
    while (!stk.empty())
    {
        if (stk.top()=='(') {  }
        else prnt += stk.top();
        stk.pop();
    }

    return prnt;
}

char buf[100000];

int main()
{
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);/**/
    //    TEST CASE     //
    int kase=1, kounter=1;/**/

    rating['/'] = 3;
    rating['*'] = 3;
    rating['-'] = 1;
    rating['+'] = 1;

    scanf("%d",&kase);
    getchar();
    gets(buf);

    while (kase--)
    {
        if (kounter++ > 1) printf("\n");


        string inp = "";
        while ( gets(buf) )
        {
            if (!strcmp(buf,"")) break;

            inp += buf;
        }

        if (inp == "") continue;
        string prnt = proc(inp);
        printf("%s\n",prnt.c_str());
    }


    return 0;
}