727 - Equation

[Jan]

I m using ms VC 6, and your code returns wrong outputs. Make a file with the inputs and run your code.

And one important thing..

Code: Select all

while(stack[k-1]!='(' && k>0)

Now if k=0 then your code first checks stack[-1], then it checks k>0. Your code will try to access negative index. So, better to use

Code: Select all

while(k>0 && stack[k-1]!='(')

Hope these help.

[newton]

Code: Select all


ACCEPTED


[abhiramn]

You are not checking for EOF. In fact the end of input is denoted by that. I had the same problem. Hope this helps.
Abhiram Natarajan.

[hamedv]

what's wrong with my code???
i'm getting WA

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <cctype>
#include <stack>

using namespace std;

int main()
{
   stack<char> mystack;
   string s;
   char c[5];
   int t;
   cin >> t;
   gets(c);
   gets(c);
   while (t--)
   {
      s = "";
      while (!mystack.empty()) mystack.pop();
      while (cin.getline(c, 5), c[0])
      {
         if (c[0] == '(')
         {
            mystack.push(c[0]);
            continue;
         }
         if (isdigit(c[0]))
         {
            s += c[0];
            continue;
         }
         if (c[0] == '+' || c[0] == '-')
         {
            if (!mystack.empty() && (mystack.top() == '*' || mystack.top() == '/'))
            {
               while(!mystack.empty() && mystack.top() != '(')
               {
                  s += mystack.top();
                  mystack.pop();
               }
               mystack.push(c[0]);
            } else mystack.push(c[0]);
            continue;
         }
         if (c[0] == '*' || c[0] == '/')
         {
            mystack.push(c[0]);
            continue;
         }
         if (c[0] == ')')
         {
            while(!mystack.empty() && mystack.top() != '(')
            {
               s += mystack.top();
               mystack.pop();
            }
            if (!mystack.empty()) mystack.pop();
         }
      }
      while(!mystack.empty())
      {
         s += mystack.top();
         mystack.pop();
      }
      cout << s << endl;
   }
}


[hamedv]

and another code with printf(), scanf()

Code: Select all

 #include <stdio.h>
#include <ctype.h>
#include <iostream>

using namespace std;

char a[100];
int i_a;

bool empty()
{
   return i_a == -1;
}

void push(char c)
{
   a[++i_a] = c;
}

void pop()
{
   if (!empty()) i_a--;
}

char top()
{
   if (!empty()) return a[i_a];
   return 0;
}

void erase()
{
   i_a = -1;
}

int size()
{
   return i_a+1;
}

int main()
{
   int t, l;
   char c, s[5];
   scanf("%d", &t);
   getchar();
   getchar();
   for (l = 0; l < t; l++)
   {
      if (l) puts("");
      erase();
      while (1)
      {
         if (scanf("%c", &c) == EOF) break;
         if (c == '\n') break;
         getchar();
         if (c == '(')
         {
            push(c);
            continue;
         }
         if (isdigit(c))
         {
            putchar(c);
            continue;
         }
         if (c == '+' || c == '-')
         {
            if (top() == '*' || top() == '/')
            {
               while (!empty() && top() != '(')
               {
                  putchar(top());
                  pop();
               }
               push(c);
            } else push(c);
            continue;
         }
         if (c == '*' || c == '/')
         {
            push(c);
            continue;
         }
         if (c == ')')
         {
            while (!empty() && top() != '(')
            {
               putchar(top());
               pop();
            }
            if (!empty()) pop();
         }
      }
      while (!empty())
      {
         putchar(top());
         pop();
      }
      puts("");
   }
   return 0;
}



[rio]

Check the io test here. You'll figure out whats wrong soon.
http://online-judge.uva.es/board/viewtopic.php?t=2592&highlight=727

(I did the same mistake )
----
Rio

[kana]

PE!!!!! what to do?

Code: Select all

   deleted


[Sohel_Cuet]

Hi kana you should print a blank line between the output lines of two consecutive inputs.Here is an example for you.

Input :

Code: Select all


2

2
+
3

3
*
4


Output :

Code: Select all

23+

34*


Hope it will work.Good Luck...

[dgsquare]

I also got WA, even I passed all of sample inputs.
Fortunately after I considered input format such as blank following character, I finally got AC.
How about checking input and output format again?

[kana]

thanx Sohel

[ishtiaq ahmed]

I cannt findout where is the error in my code. Here is my code

Code: Select all

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


int taking_input(void);
void processing(void);
int pop(int);
void _calling(int);


struct x
{
   char given_input[100000];
};
typedef struct x info;




char expression[100000], stack[100000];
info data[1000];



int taking_input(void)
{
   int _cas;
   char ch, str[10000],indexx=-1,n=-1;
   scanf("%d%*c%*c",&_cas);
   while( (ch = getchar()) != EOF )
   {
      if(ch == '\n')
      {   
         str[++indexx] = NULL;
         strcpy(data[++n].given_input,str);
         indexx = -1;
      }
      else if(ch != '\n')
      {
         str[++indexx] = ch;
         scanf("%*c");
      }

   }
   if(n<_cas-1)
   {
      str[++indexx] = NULL;
      strcpy(data[++n].given_input,str);
   }
   return _cas;
}



void _calling(int _cas)
{
   int i;
   for(i=0;i<_cas;i++)
   {
      strcpy(expression,data[i].given_input);
      processing();
      puts("");
   }
}


void processing()
{
   int i,top=-1;
   for(i=0;expression[i];i++)
   {
      if(expression[i] >= '0' && expression[i] <= '9')
         printf("%c",expression[i]);
      else
      {
         if(expression[i] == '(')
            stack[++top] = '(';
         else if(expression[i] == ')')
         {
            while(stack[top] != '(')
            {
               printf("%c",stack[top--]);
            }
            top--;
         }
         else if(expression[i] == '*')
         {
            stack[++top]='*';
            if((top - 1) > -1 && (stack[top - 1] == '/'))
            {
               top = pop(top);
               stack[top] = '*';
            }

         }
         else if(expression[i] == '/')
         {
            stack[++top]='/';
            if((top - 1) > -1 && stack[top - 1] == '*')
            {
               top = pop(top);
               stack[top] = '/';
            }

         }
         else if(expression[i] == '+')
         {
            stack[++top]='+';
            if((top - 1) > -1 && (stack[top - 1] == '-' || stack[top -1] == '*' || stack[top -1] == '/' || stack[top -1] == '+'))
            {
               top = pop(top);
               stack[top] = '+';
            }

         }
         else if(expression[i] == '-')
         {
            stack[++top]='-';
            if((top - 1) > -1 && (stack[top - 1] == '+' || stack[top -1] == '*' || stack[top -1] == '/' || stack[top -1] == '-'))
            {
               top=pop(top);
               stack[top] = '-';
            }

         }

      }
   }
   while(top>-1)
   {
      printf("%c",stack[top--]);
   }
}
   



int pop(int top)
{
   printf("%c",stack[top - 1]);
   top--;
   return top;
}



int main()
{
   //freopen("c:\\input.txt","r",stdin);
   int _cas;
   _cas = taking_input();
   _calling(_cas);
   return 0;
}



[sclo]

To solve this problem, do recursive descent parsing, then just do dfs on the parse tree. Trying to do it with a stack is a source of trouble.

[Ron]

why TLE....

Code: Select all

CODE ACCEPTED

Please help me.......

[Jan]

Your code looks correct. I submitted it and got accepted.

[Ron]

To Jan ,
Thank U very much .!!!!!
I submitted it 3-4 times,and I was getting TLE.. .Now i accepted in 2.250...!!