Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > c > answers

conversion from infix to postfix

Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#1: Sep 17 '06
Hi... I need a program to convert an infix arithmetic expression to postfix with the use of stacks... Can anyone tell me how do i go about implementing this? thanks

D_C D_C is offline
Needs Regular Fix
  
Join Date: Jun 2006
Posts: 294
#2: Sep 17 '06

re: conversion from infix to postfix

There is a standard algorithm to do this. The last paragraph of this website has the steps.

Print the numbers out in normal order, push parenthesis and operators onto the stack. When parenthesis line up, ignore them, don't print anything. If they don't line up, that's an error. Then, depending upon priority of the operator (PEMDAS) push or pop the operator off the stack. If you pop it, display it in the output.

The website explains it better, why don't you go have a look.
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#3: Sep 20 '06

re: conversion from infix to postfix

Hi can anyone help me to check this... Im lost in my own program... I noe some part of it is wrong... can anyone tell me... thanks

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
using namespace std;

int main()
{
string line, str;
int number;

cout<<"Sample Input 1"<<" "<<endl;
cin>>line;

getline(cin, line);
istringstream iss(line); //create string stream

while(!iss.eof())
{
iss >> str; //reads from iss into str until next space is met
}

//Postfix evaluation
int eval_postfix(const vector<char>&v, stack<int>&st)
{
for (vector<char>::const_iterator str = v.begin(begin(); str !=v.end(); ++str)
{
if ('0'<= str && str<='9')
st.push(str-'0')
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

if (str == "+" || str == "-") //when you compare for char, it's '+' and '-'
{
case '+': result = arg1 + arg2;
return 1;
break;
case '-': result = arg1 - arg2;
resturn 2;
break;
}
else if (str == "*" || str == "/")
{
case '*': result = arg1 * arg2;
break;
return 3;
case '/': result = arg1 / arg2;
break;
return 4;
} //end if else

st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix


system("pause");
return 0;
}
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#4: Sep 20 '06

re: conversion from infix to postfix

Hi i modify my codes but i'm unable to execute it.... can anyone help me to spot the mistake.. thanks

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <sstream>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.       string line, str;  
  10.       int number;
  11.  
  12.       cout<<"Sample Input:"<<" "<<endl;
  13.       cin>>line;
  14.  
  15.       getline(cin, line);
  16.       istringstream iss(line); //create string stream
  17.  
  18.       while(!iss.eof()) 
  19.       {
  20.            iss >> str; //reads from iss into str until next space is met
  21.       }
  22.  
  23.       //Code of Postfix Evaluation
  24.       int eval_postfix(const vector<char>&v, stack<int>&st)
  25.       {
  26.           for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
  27.           {
  28.               if ('0'<= *ptr && *ptr<='9')
  29.               st.push(*ptr-'0')
  30.               else
  31.               {
  32.                   int arg2 = st.top();
  33.                   st.pop();
  34.                   int arg1 = st.top();
  35.                   st.pop();
  36.                   int result;
  37.  
  38.               switch (*ptr)
  39.               {
  40.                      case '+': result = arg1 + arg2;
  41.                      break;
  42.                      case '-': result = arg1 - arg2;
  43.                      break;
  44.                      case '*': result = arg1 * arg2;
  45.                      break;
  46.                      case '/': result = arg1 / arg2;
  47.                      break; 
  48.               } //end switch
  49.               st.push(result);
  50.               } //end else
  51.           }//end for
  52.  
  53.           int i = st.top();
  54.           st.pop();
  55.           return i;
  56.       }//end eval_postfix 
  57.  
  58.        cout<<i<<"Sample Output:"<<" "<<endl;
  59.  
  60.        system("pause");
  61.        return 0;
  62. }
  63.  
Banfa's Avatar
Administrator
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,461
#5: Sep 20 '06

re: conversion from infix to postfix

You have tried to define the function

int eval_postfix(const vector<char>&v, stack<int>&st)

inside the function

int main()

This is not allowed in C/C++ move the definition of the function eval_postfix outside the function main.
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#6: Sep 20 '06

re: conversion from infix to postfix

Hi... I put the "int eval_postfix(const vector<char>&v, stack<int>&st)" out of the main, i still get error.. the error i get is something to do with this "int main()".. but i cant remove the "int main()"..... I'm sory to bother u but im really weak in my programming...

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
using namespace std;
int eval_postfix(const vector<char>&v, stack<int>&st)
int main()
{
string line, str;
int number;
char *cstr;

cout<<"Sample Input:"<<" "<<endl;
cin>>line;

getline(cin, line);
istringstream iss(line); //create string stream

while(!iss.eof())
{
iss >> str; //reads from iss into str until next space is met
}

//Code of Postfix Evaluation
for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
{
if ('0'<= *ptr && *ptr<='9')
st.push(*ptr-'0')
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

switch (*ptr)
{
case '+': result = arg1 + arg2;
break;
case '-': result = arg1 - arg2;
break;
case '*': result = arg1 * arg2;
break;
case '/': result = arg1 / arg2;
break;
} //end switch
st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix

//convert string to integer
number = atoi(str.c_str()); //now number is 1234

//convert integer into string
sprintf(cstr, "%d", number); //print number into cstring
string str(cstr); //makes cstring a string

//checking if all characters of the string are digits
cstr = str.c_str();
if ( isdigit(*cstr) ) //checks the first character of cstr is digit or not
return true;

cout<<"Sample Output:"<<cin<<" "<<endl;

system("pause");
return 0;
}
Banfa's Avatar
Administrator
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,461
#7: Sep 20 '06

re: conversion from infix to postfix

You have to move the entire function, not just the header line

This
Expand|Select|Wrap|Line Numbers
  1. int main()
  2. {
  3.   // main code
  4.  
  5.   int fn()
  6.   {
  7.     // function code
  8.   }
  9.  
  10.   // more main code
  11. }
  12.  
becomes

Expand|Select|Wrap|Line Numbers
  1. int fn();
  2.  
  3. int main()
  4. {
  5.   // main code
  6.  
  7.   // more main code
  8. }
  9.  
  10. int fn()
  11. {
  12.   // function code
  13. }
  14.  
  15.  
  16.  
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#8: Sep 20 '06

re: conversion from infix to postfix

for this function, for the 2nd sentence , may i noe how do i declare "begin"? i hav error regarding this.... should i declare it in main function or in its own function itself...

int eval_postfix(const vector<char>&v, stack<int>&st)
{
for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
{
if ('0'<= *ptr && *ptr<='9')
st.push(*ptr-'0');
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

switch (*ptr)
{
case '+': result = arg1 + arg2;
break;
case '-': result = arg1 - arg2;
break;
case '*': result = arg1 * arg2;
break;
case '/': result = arg1 / arg2;
break;
} //end switch
st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix
Banfa's Avatar
Administrator
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,461
#9: Sep 20 '06

re: conversion from infix to postfix

Not really sure what you are saying but

for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)

should be

for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#10: Sep 20 '06

re: conversion from infix to postfix

Thanks Banfa for ur help.... but do u mind helping me to check my program please.... I've been struggling from juz now and i still cant do it....

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <sstream>
  5. using namespace std;
  6.  
  7. int eval_postfix(const vector<char>&v, stack<int>&st);
  8. int main()
  9. {
  10.       string line, str;
  11.       int number;
  12.       char *cstr;
  13.  
  14.       cout<<"Sample Input:"<<" "<<endl;
  15.       cin>>line;
  16.  
  17.       getline(cin, line);
  18.       istringstream iss(line); //create string stream
  19.  
  20.       while(!iss.eof()) 
  21.       {
  22.        iss >> str; //reads from iss into str until next space is met
  23.       }
  24.  
  25.       //convert string to integer
  26.       number = atoi(str.c_str()); //now number is 1234
  27.  
  28.       cout<<"Sample Output:"<<str<<" "<<endl;
  29.  
  30.       system("pause");
  31.       return 0;
  32. }
  33.  
  34.      //Code of Postfix Evaluation
  35.       int eval_postfix(const vector<char>&v, stack<int>&st)
  36.       {
  37.           for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  38.           {
  39.               if ('0'<= *ptr && *ptr<='9')
  40.               st.push(*ptr-'0');
  41.               else
  42.               {
  43.                   int arg2 = st.top();
  44.                   st.pop();
  45.                   int arg1 = st.top();
  46.                   st.pop();
  47.                   int result;
  48.  
  49.               switch (*ptr)
  50.               {
  51.                      case '+': result = arg1 + arg2;
  52.                      break;
  53.                      case '-': result = arg1 - arg2;
  54.                      break;
  55.                      case '*': result = arg1 * arg2;
  56.                      break;
  57.                      case '/': result = arg1 / arg2;
  58.                      break; 
  59.               } //end switch
  60.               st.push(result);
  61.               } //end else
  62.           }//end for
  63.  
  64.           int i = st.top();
  65.           st.pop();
  66.           return i;
  67.       }//end eval_postfix 
  68.  
  69.       //Conversion from Infix to Postfix expression
  70.       vector<char> postFix;
  71.       for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  72.       {
  73.         switch(ch)
  74.         {
  75.                   case operand: 
  76.                        postfixExp = postfixExp + ch;
  77.                        break;
  78.                   case '(': 
  79.                        Stack.push (ch);
  80.                        Break;
  81.                   case ')':
  82.                        while (stack.top()!='(')
  83.                        {
  84.                              postfixExp = postfixExp + stack.top();
  85.                              Stack.pop();
  86.                        } //end while
  87.  
  88.                        Stack.pop();
  89.                        break;
  90.  
  91.                   //infix to postfix - use stack for storing operators
  92.                   case operator:
  93.  
  94.                        while (!Stack.isEmpty() && Stack.top != '(' && precedence(ch) >= precedence(stack.top()))
  95.                        {
  96.                              postfixExp = postfixExp + Stack.top();
  97.                              Stack.pop();
  98.                         } end while
  99.              }//end switch
  100.  
  101.     } //end for
  102.  
  103.     while (!Stack.isEmpty())
  104.     {
  105.           postfixExp = postfixExp + Stack.top();
  106.           Stack.pop()
  107.     }// end while
  108.  
Banfa's Avatar
Administrator
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,461
#11: Sep 20 '06

re: conversion from infix to postfix

None of this code

Expand|Select|Wrap|Line Numbers
  1.       //Conversion from Infix to Postfix expression
  2.       vector<char> postFix;
  3.       for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  4.       {
  5.         switch(ch)
  6.         {
  7.                   case operand: 
  8.                        postfixExp = postfixExp + ch;
  9.                        break;
  10.                   case '(': 
  11.                        Stack.push (ch);
  12.                        Break;
  13.                   case ')':
  14.                        while (stack.top()!='(')
  15.                        {
  16.                              postfixExp = postfixExp + stack.top();
  17.                              Stack.pop();
  18.                        } //end while
  19.  
  20.                        Stack.pop();
  21.                        break;
  22.  
  23.                   //infix to postfix - use stack for storing operators
  24.                   case operator:
  25.  
  26.                        while (!Stack.isEmpty() && Stack.top != '(' && precedence(ch) >= precedence(stack.top()))
  27.                        {
  28.                              postfixExp = postfixExp + Stack.top();
  29.                              Stack.pop();
  30.                         } end while
  31.              }//end switch
  32.  
  33.     } //end for
  34.  
  35.     while (!Stack.isEmpty())
  36.     {
  37.           postfixExp = postfixExp + Stack.top();
  38.           Stack.pop()
  39.     }// end while
  40.  
Is inside a function and is causing a syntax error

It doesn't appear to have any purpose so I guess you can just delete it as the program compiles fine without it.
Nhd Nhd is offline
Newbie
  
Join Date: Aug 2006
Posts: 24
#12: Sep 20 '06

re: conversion from infix to postfix

hi Banfa.. my purpose in typing out those codes is to convert infix to postfix..

for example:
Sample input 1
1 + 2 * 3 - 4 / 2 + 5 * 6
Sample output 1
35

Sample input 2
( 10 + 20 ) * 30 - 4000 / 20 + 50 * 60
Sample output 2
3700

I'm trying to write a program for this... and my notes shows only these codes, the one that i type out...

what should i do now... :(
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/other

Forums
Visit our community forums for general discussions and latest on Bytes

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 229,155 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved