Entry

C++: Simple: How to convert infix to suffix? [Bracket]

Jan 9th, 2004 22:17
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 04 January 2004 - 05:52 pm --------------------

C++: Simple: How to convert infix to suffix? [Bracket]

---

Steps: Overview:

 1. -Create a new C++ application

 2. -Fill in the following code

--- cut here ---------------------------------------------------------

#include <iostream> // note no .h

#include <string>

using namespace std;

//

 class CLASSStringConvertInfixToSuffix {

  //

  private:

   //

   string expressionS;

   string tabletokenS;

   string tableinputS;

   string tablestackS;

   string stackS;

   string kexpressionS;

   string kstackS;

   string resultS;

   int expressionI;

   int stackI;

   int posI;

   int priorityinputI;

   int prioritystackI;

   int I;

   //

  public:

   CLASSStringConvertInfixToSuffix( string expressionS ); // 
constructor

   ~CLASSStringConvertInfixToSuffix(); // destructor

   string FNStringConvertInfixToPrefixS();

 };

 //

 // constructor for this class

 CLASSStringConvertInfixToSuffix::CLASSStringConvertInfixToSuffix( 
string expressionS ) {

  this->expressionS = expressionS;

  tabletokenS = "#-+*/^abcdefghijklmnopqrstuvwxyz0123456789()";

  tableinputS = "03344599999999999999999999999999999999999992";

  tablestackS = "03344599999999999999999999999999999999999929";

  stackS = "";

  kexpressionS = "";

  kstackS = "";

  resultS = "";

  expressionI = 0 - 1;

  stackI = 0 - 1;

  posI = -1;

  priorityinputI = -1;

  prioritystackI = -1;

  I = 0;

  stackI = stackI + 1;

  stackS = "#";

 };

 //

 // destructor for this class

 CLASSStringConvertInfixToSuffix::~CLASSStringConvertInfixToSuffix() {

 };

 //

 string CLASSStringConvertInfixToSuffix::FNStringConvertInfixToPrefixS
() {

  do {

   expressionI = expressionI + 1;

   kexpressionS = expressionS.substr( expressionI, 1 );

   posI = tabletokenS.find( kexpressionS, 0 );

   if ( posI == -1 ) {

    cout << kexpressionS + " not found in tabletokenS " + tabletokenS 
<< endl;

    return( "error" );

   }

   priorityinputI = atoi( tableinputS.substr( posI, 1 ).c_str() );

   kstackS = stackS.substr( 0, 1 );

   posI = tabletokenS.find( kstackS, 0 );

   if ( posI < 0 ) {

    cout << kstackS + " not found in tabletokenS " + tabletokenS << 
endl;

    return( "error" );

   }

   prioritystackI = atoi( tablestackS.substr( posI, 1 ).c_str() );

   if ( priorityinputI > prioritystackI ) {

    stackS = kexpressionS + stackS;

   }

   else {

    do {

     if ( ( kstackS != "(" ) && ( kstackS != ")" ) ) {

      resultS = resultS + kstackS;

     }

     stackS = stackS.substr( 1, stackS.length() );

     kstackS = stackS.substr( 0, 1 );

     posI = tabletokenS.find( kstackS, 0 );

     if ( posI < 0 ) {

      cout << kstackS + " not found in tabletokenS " + tabletokenS << 
endl;

      return( "error" );

     }

     prioritystackI = atoi( tablestackS.substr( posI, 1 ).c_str() );

    } while ( priorityinputI <= prioritystackI );

    stackS = kexpressionS + stackS;

   }

  } while ( expressionI < ( expressionS.length() - 1 ) );

  I = 0 - 1;

  do {

   I = I + 1;

   kstackS = stackS.substr( I, 1 );

   if ( ( kstackS != "#" ) && ( kstackS != "(" ) && ( kstackS !
= ")" ) ) {

    resultS = resultS + kstackS;

   }

  } while ( I < ( stackS.length() - 1 ) );

  return( resultS );

 };

 //

 main() {

  string infixS = "((2*3)^6+(4*5)+(6*7))^7";

  CLASSStringConvertInfixToSuffix OBJECTrpn( infixS );

  cout << "infix = " << infixS << endl;

  cout << "suffix = " << OBJECTrpn.FNStringConvertInfixToPrefixS() << 
endl;

  cin >> "";

 }

//

--- cut here ---------------------------------------------------------

 3. -Run this code

     That should show:

      ((2*3)^6+(4*5)+(6*7))^7

      resultS is 23*6^45*+67*+7^

      which is respectively the infix and suffix representation.

 4. -Change expressionS to your own infix string

      e.g.

       expressionS = "(3+4)*5+6-7"

     and recompile for another example

     ---

      Note:

       In order to keep it very simple and short in this 
implementation:

       1. Please take spaces away.

          so "(3+4)*5+6-7" is OK,

          but "( 3 + 4 ) * 5 + 6 - 7" is not.

       2. only single characters (like a, b, c, ..., 3, 4, 5, ...)

           so "a+b*c-d^f" is OK,
           but "alpha*beta+gamma" is not.

       3. the priorities should here be single numbers between 0 and 9
          (like 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
          in your tables.

       4. This program is a direct translation of the Dijkstra double
          priority algorithm (see below for the link and further 
description)

---
---

Note:

Compiled successfully as a console application in:

- Microsoft Visual Studio C++.NET 

- Borland C++ free command line compiler v5.5

- Borland C++Builder v6, where this main was used:

//---------------------------------------------------------------------

#pragma argsused

int main(int argc, char* argv[])
{
  string infixS = "((2*3)^6+(4*5)+(6*7))^7";

  CLASSStringConvertInfixToSuffix OBJECTrpn( infixS );

  cout << "infix = " << infixS << endl;

  cout << "suffix = " << OBJECTrpn.FNStringConvertInfixToPrefixS() << 
endl;

  cin >> "";

   return 0;
}
//---------------------------------------------------------------------

---
---

Internet: see also:

---

Algorithm: Expression: Infix: Convert: Postfix: Overview: How convert 
infix to postfix expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26071/fid/585

----------------------------------------------------------------------