Infix notation to Reverse Polish Notation - C++ Snipplr Social Repository

Revision: 8879

at October 13, 2008 22:05 by Mcgee_00

Updated Code

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

using namespace std;

char pop(list<char> & a)                 //Pops the stack and returns it, I use it to append to output vector
{
    char result = a.front();
    a.pop_front();
    return result;
}


int main()
{
    int num;
    string in;
    cin >> num;

    string out;                                              //stores outputed characters front operator stack
    list<char> opr;
    for(int zed=0; zed<num; zed++) {
    cin >> in;

    for(int i =0; i < in.length(); i++)
    {
        switch(in[i])                                         //Gets operator gets their precedence and pushes them into the stack(list) and
                                                              //output string
        {
            case '(': opr.push_front(in[i]);
                      break;
            case ')':  while(opr.front()!='(' && !opr.empty())
                       {
                          out.push_back(pop(opr));
                       }

                      opr.pop_front();
                      break;
            case '-': if(opr.front() == '+' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '+': if(opr.front() == '-' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '*': if(opr.front() == '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '^': opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '/': if(opr.front() == '^' || '*' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            default: if(isdigit(in[i]) || isalpha(in[i]))   //Default: if character is a digit or a letter append it to output
                out.push_back(in[i]);
        }

    }

    while(!opr.empty())                     //if the stack isn't empty push the rest into the output vector
        {
            out.push_back(pop(opr));
            opr.pop_front();
        }

    out.erase(remove(out.begin(), out.end(),'('), out.end());  //remove those stupid parenthesis
    out.push_back('\n');
}

cout << out;

    return 0;
}

Revision: 8878

at October 13, 2008 17:30 by Mcgee_00

Updated Code

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

using namespace std;

char pop(list<char> & a)                 //Pops the stack and returns it, I use it to append to output vector
{
    char result = a.front();
    a.pop_front();
    return result;
}


int main()
{
    int num;
    string in;
    cin >> num;

    string out;                                              //stores outputed characters front operator stack
    list<char> opr;
    string::iterator i;

    for(int zed=0; zed<num; zed++) {

    cin >> in;

    for(int i =0; i < in.length(); i++)
    {
        switch(in[i])                                         //Gets operator gets their precedence and pushes them into the stack(list) and
                                                              //output string
        {
            case '(': opr.push_front(in[i]);
                      break;
            case ')':  while(opr.front()!='(' && !opr.empty())
                       {
                          out.push_back(pop(opr));
                       }

                      opr.pop_front();
                      break;
            case '-': if(opr.front() == '+' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '+': if(opr.front() == '-' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '*': if(opr.front() == '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '^': opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '/': if(opr.front() == '^' || '*' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            default: if(isdigit(in[i]) || isalpha(in[i]))   //Default: if character is a digit or a letter append it to output
                out.push_back(in[i]);
        }

    }

    while(!opr.empty())                     //if the stack isn't empty push the rest into the output vector
        {
            out.push_back(pop(opr));
            opr.pop_front();
        }

    out.erase(remove(out.begin(), out.end(),'('), out.end());  //remove those stupid parenthesis
    out.push_back('\n');
}

cout << out;

    return 0;
}

Revision: 8877

at October 12, 2008 08:54 by Mcgee_00

Updated Code

#include <iostream>
#include <cctype>
#include <string>
#include <vector>
#include <list>

using namespace std;

char pop(list<char> & a)                 //Pops the stack and returns it, I use it to append to output vector
{
    char result = a.front();
    a.pop_front();
    return result;
}

void show(const char &s)
{
    cout << s;
}

void show2(vector<char> v)              //Shows final output
{
    for_each(v.begin(), v.end(), show);
}

int main()
{
    int num;
    string in;
    cin >> num;

    vector<char> out;
    list<char> opr;
    vector<vector<char> > rpn;

for(int zed=0; zed<num; zed++) {

    cin >> in;
    int length = sizeof in;
    for(int i =0; i < in.length(); i++)
    {

        switch(in[i])                                         //Gets operator gets their precedence and pushes them into the stack(list) and
                                                              //output vector
        {
            case '(': opr.push_front(in[i]);
                      break;
            case ')':  while(opr.front()!='(' && !opr.empty())
                       {
                          out.push_back(pop(opr));
                       }

                      opr.pop_front();
                      break;
            case '-': if(opr.front() == '+' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '+': if(opr.front() == '-' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '*': if(opr.front() == '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '^': opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '/': if(opr.front() == '^' || '*' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            default: if(isdigit(in[i]) || isalpha(in[i]))   //Default: if character is a digit or a letter append it to output
            out.push_back(in[i]);
        }

    }

    while(!opr.empty())                     //if the stack isn't empty push the rest into the output vector
        {
            out.push_back(pop(opr));
            opr.pop_front();
        }

    out.erase(remove(out.begin(), out.end(),'('), out.end());  //remove those stupid parenthesis
    out.push_back('\0');                                       //terminate it with a null character
    rpn.push_back(out);

    out.empty();

}

for_each(rpn.begin(), rpn.end(), show2);


    return 0;
}

Revision: 8876

at October 12, 2008 08:52 by Mcgee_00

Updated Code

#include <iostream>
#include <cctype>
#include <string>
#include <vector>
#include <list>

using namespace std;

char pop(list<char> & a)                 //Pops the stack and returns it, I use it to append to output vector
{
    char result = a.front();
    a.pop_front();
    return result;
}

void show(const char &s)
{
    cout << s;
}

void show2(vector<char> v)              //Shows final output
{
    for_each(v.begin(), v.end(), show);
}

int main()
{
    int num;
    string in;
    cin >> num;

    vector<char> out;
    list<char> opr;
    vector<vector<char> > rpn;

for(int zed=0; zed<num; zed++) {

    cin >> in;
    int length = sizeof in;
    for(int i =0; i < in.length(); i++)
    {

        switch(in[i])                                         //Gets operator gets their precedence and pushes them into the stack(list) and
                                                              //output vector
        {
            case '(': opr.push_front(in[i]);
                      break;
            case ')':  while(opr.front()!='(' && !opr.empty())
                       {
                          out.push_back(pop(opr));
                       }

                      opr.pop_front();
                      break;
            case '-': if(opr.front() == '+' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '+': if(opr.front() == '-' || '*' || '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '*': if(opr.front() == '^' || '/' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '^': opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            case '/': if(opr.front() == '^' || '*' || '%')
                      {
                          out.push_back(pop(opr));
                          opr.push_front(in[i]);
                      }
                      else opr.push_front(in[i]);
                      out.push_back(' ');
                      break;
            default: if(isdigit(in[i]) || isalpha(in[i]))
            out.push_back(in[i]);
        }

    }

    while(!opr.empty())                     //if the stack isn't empty push the rest into the output vector
        {
            out.push_back(pop(opr));
            opr.pop_front();
        }

    out.erase(remove(out.begin(), out.end(),'('), out.end());  //remove those stupid parenthesis
    out.push_back('\0');
    rpn.push_back(out);

    out.empty();

}

for_each(rpn.begin(), rpn.end(), show2);


    return 0;
}

Revision: 8875

at October 11, 2008 19:16 by Mcgee_00

Initial Code

#include <iostream>
#include <cctype>
#include <string>
#include <vector>
#include <list>

using namespace std;

char pop(list<char> & a)
{
    char result = a.front();
    a.pop_front();
    return result;
}

void show(const char &s)
{
    cout << s;
}

int main()
{
    int num;
    string in;
    cin >> num;

    vector<char> out[num];
    list<char> opr[num];

for(int zed=0; zed<num; zed++) {
    cin >> in;
    for(int i =0; i < in.length(); i++)
    {

        switch(in[i])
        {
            case '(': opr[zed].push_front(in[i]);
                      break;
            case ')':  while(opr[zed].front()!='(' && !opr[zed].empty())
                       {
                          out[zed].push_back(pop(opr[zed]));
                       }

                      opr[zed].pop_front();
                      break;
            case '-': if(opr[zed].front() == '+' || '*' || '^' || '/' || '%')
                      {
                          out[zed].push_back(pop(opr[zed]));
                          opr[zed].push_front(in[i]);
                      }
                      else opr[zed].push_front(in[i]);
                      out[zed].push_back(' ');
                      break;
            case '+': if(opr[zed].front() == '-' || '*' || '^' || '/' || '%')
                      {
                          out[zed].push_back(pop(opr[zed]));
                          opr[zed].push_front(in[i]);
                      }
                      else opr[zed].push_front(in[i]);
                      out[zed].push_back(' ');
                      break;
            case '*': if(opr[zed].front() == '^' || '/' || '%')
                      {
                          out[zed].push_back(pop(opr[zed]));
                          opr[zed].push_front(in[i]);
                      }
                      else opr[zed].push_front(in[i]);
                      out[zed].push_back(' ');
                      break;
            case '^': opr[zed].push_front(in[i]);
                      out[zed].push_back(' ');
                      break;
            case '/': if(opr[zed].front() == '^' || '*' || '%')
                      {
                          out[zed].push_back(pop(opr[zed]));
                          opr[zed].push_front(in[i]);
                      }
                      else opr[zed].push_front(in[i]);
                      out[zed].push_back(' ');
                      break;
            default: if(isdigit(in[i]) || isalpha(in[i]))
            out[zed].push_back(in[i]);
        }

    }

    while(!opr[zed].empty())
        {
            out[zed].push_back(pop(opr[zed]));
            opr[zed].pop_front();
        }

    out[zed].erase(remove(out[zed].begin(), out[zed].end(),'('), out[zed].end());

}

    for(int y=0; y < num; y++){
        cout << endl;
        for_each(out[y].begin(), out[y].end(), show);
        }

    return 0;
}

Initial URL

Initial Description

The bugged version: Somehow, it prints random characters to me like [] except the spaces filled in and other accented letters when I input more parenthesis and longer input. 

How to use: example-> 
input:
3
1+2
(1+2)*(6-2)
6-7*(9*10)/8 

output: 
1 2 +
1 2 + 6 2 - *
6 7 - 9 10 ** 8 /

Initial Title

Infix notation to Reverse Polish Notation

Initial Tags

Initial Language

C++

Choose a language for easy browsing: