[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;
}

[UVa] 392 - Polynomial Showdown

Just conditioning, loads of ifs

If you're getting PE or WA just test with some isolated values for different coefficients. Some of my test cases are.

0    0    0    1   22 -333    0    1   -1
0    0    0    0    0    0  -55    5    0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 -1 0
0 0 0 0 0 0 -1 0 0
0 0 0 0 0 -1 0 0 0
0 0 0 0 -1 0 0 0 0
0 0 0 -1 0 0 0 0 0
0 0 -1 0 0 0 0 0 0
0 -1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

x^5 + 22x^4 - 333x^3 + x - 1
-55x^2 + 5x
0
-1
-x
-x^2
-x^3
-x^4
-x^5
-x^6
-x^7
-x^8
0

#include <stdio.h>
#include <string.h>

int a[10];

int main()
{
    int i, print, z;
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);
    while (scanf("%d %d %d %d %d %d %d %d %d",&a[8],&a[7],&a[6],&a[5],&a[4],&a[3],&a[2],&a[1],&a[0])==9)
    {
        for (i=0, z=1 ; i<9 && z; i++)      //-----|Checking if the
            if (a[i]) z=0;                  //-----|polynomial is zero

        if (z) {                            //-----|The polynomial is found
            printf("0\n");                  //-----|to be zero in fact
            continue;
        }

    //-[ The first value of the equation is not printed yet ]
        print=0;
        for (i=8 ; i>1 ; i--)
        {
            if (print && a[i]) printf(" ");

            if (a[i]==-1)
            {
                (print? printf("- x^%d",i) : printf("-x^%d",i) );
            } else if (a[i]==1)
            {
                (print? printf("+ x^%d",i) : printf("x^%d",i) );
            } else if (a[i]<0)
            {
                (print? printf("- %dx^%d",-1*a[i],i) : printf("%dx^%d",a[i],i) );
            } else if (a[i])
            {
                (print? printf("+ %dx^%d",a[i],i) : printf("%dx^%d",a[i],i) );
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]==-1)
            {
                (print? printf("- x") : printf("-x") );
            } else if (a[i]==1)
            {
                (print? printf("+ x") : printf("x") );
            } else if (a[i]<0)
            {
                (print? printf("- %dx",-1*a[i]) : printf("%dx",a[i]) );
            } else if (a[i])
            {
                (print? printf("+ %dx",a[i]) : printf("%dx",a[i]));
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        i--;
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]<0)
            {
                (print ? printf("- %d",-1*a[i]) : printf("%d",a[i]) );
            } else if (a[i])
            {
                (print ? printf("+ %d",a[i]) : printf("%d",a[i]) );
            }
        }

        printf("\n");
    }
    return 0;
}

[UVa] 343 - What base is this?

I was too lazy when I saw this problem for the very first time 2 years ago. Solving problems that required parsing a string were too tedious for me back then. Well, guess what it generated a great code for future problems from this domain.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define isChar(i) ((i>='A'&&i<='Z')||(i>='0'&&i<='9'))
typedef unsigned long long ULL;
int vals[1000];
char input[1000], val1[1000], val2[1000];
ULL getVal(char *a, int base, int ln)
{
    int len = ln, i;
    ULL val=0;
    for (i=len-1 ; i>=0 ; i--)
    {
        val = val + (vals[a[i]]) * (int)pow((double)base,(len-1-i));
    }
    return val;
}

int setVals()
{
    int i;
    for (i=0 ; i<=9 ; i++)
    {
        vals[i+'0'] = i;
    }
    for (i='A' ; i<='Z' ; i++)
    {
        vals[i] = (i-55);
    }
}

int parser(char *a, int *l1, int *l2, int *mb1, int *mb2)
{
    int i, j, min;
    for (i=0 ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val1[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val1[j]='\0';
    *l1=j;
    *mb1=min+1;

    for ( ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val2[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val2[j]='\0';
    *l2=j;
    *mb2=min+1;
}

int main()
{
    int l1, l2, minb1, minb2, f, i, j;
    setVals();

    while (gets(input))
    {
        parser(input,&l1,&l2,&minb1,&minb2);

        f=0;

        for (i=(minb1>1?minb1:2) ; i<=36 && !f ; i++)
        {
            for (j=(minb2>1?minb2:2) ; j<=36 && !f ; j++)
            {
                if (getVal(val1,i,l1) == getVal(val2,j,l2))
                {
                    printf("%s (base %d) = %s (base %d)\n",val1,i,val2,j);
                    f=1;
                }
            }
        }

        if (!f) printf("%s is not equal to %s in any base 2..36\n",val1,val2);

    }
    return 0;
}