Wednesday, September 21, 2016
UVa 727 Equation
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 dont because my code doesnt take them into account.
Sample Input:
Tricky case: None that comes to mind. Even though some people are saying that cases like (1+2)3 exist, they dont because my code doesnt take them into account.
Sample Input:
Sample Output:
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
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 arrays 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(" ");
string inp = "";
while ( gets(buf) )
{
if (!strcmp(buf,"")) break;
inp += buf;
}
if (inp == "") continue;
string prnt = proc(inp);
printf("%s ",prnt.c_str());
}
return 0;
}
Go to link download
