infix to postfix conversion for exponentiation operation

Question

I am learning polish notation and i tried a program for infix to postfix conversion.

My program executed in a fine manner for operators like + and - . But for exponentiation operation which is right associative its not working correctly.

For eg: The expression A^B^C should be converted to ABC^^ , while the algorithm i used it is converting it into AB^C^.

The Algorithm used is:

Define a stack array.
Scan each character in the infix string
If it is between 0 to 9, append it to postfix string.
If it is left parenthesis push to stack
If it is operator *,+,-,/,%,^ then 
          If the stack is empty push it to the stack
          If the stack is not empty then start a loop:
                             If the top of the stack has higher precedence
                             Then pop and append to output string
                             Else break
                     Push to the stack

If it is right parenthesis then
            While stack not empty and top not equal to left brace
            Pop from stack and append to output string
            Finally pop out the left brace.

If there is any input in the stack pop and append to the Postfix string.

What changes should i make in the algorithm so that it works for right associative operators too.?.

My code is :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
# define MAX 100
int top=-1;
char infix[100],postfix[100];
char stack[100];
int priority(char symbol)
{
    switch(symbol)
    {
        case '(':return 0;
        case '+':
        case '-':
                 return 1;
        case '/':
        case '*':
        case '%':
                 return 2;
        case '^':
                 return 3;
        default :return 0;
    }
}
void push(char symbol)
{
    if(top==MAX-1)
    {
        printf("Stack overflow:\n");
        exit(1);
    }
    top=top+1;
    stack[top]=symbol;
}
char pop()
{
    if(top==-1)
    {
        printf("Stack underflow:\n");
        exit(1);
    }
    return stack[top--];
}
void infix_to_postfix()
{
    int i,p=0;
    char symbol,next;
    for(i=0;i<strlen(infix);i++)
    {
        symbol=infix[i];

            switch(symbol)
            {
                case '(':push(symbol);
                         break;
                case ')':while((next=pop())!='(') 
                         {
                            postfix[p]=next;
                            p++;
                         }
                         break;
                case '+':
                case '-':
                case '*':
                case '/':
                case '%':
                case '^':
                while(top!=-1 && priority(stack[top])>=priority(symbol))
                {//or stack is empty
                    postfix[p]=pop();
                    p++;
                }
                push(symbol);
                break;
                default://if operand comes
                postfix[p]=symbol;
                p++;
            }
    }
    while(top!=-1)
    {
        postfix[p]=pop();
        //printf("%c",pop());
        p++;
    }
    postfix[p]='\0';
}
int main()
{
    printf("Enter the infix expression:\n");
    scanf("%s",infix);
    printf("The post fix expression is:\n");
    infix_to_postfix();
    printf("->  %s",postfix);
    return 0;
}

Answer 1

Hope this doesn't sound too pedantic, but I would suggest you to change the whole approach of the algorithm. Since this approach really needs a lot of tunning every time you add a new operator. Even more so, as operators go getting more complicated, your method will become extremely inpractical.

I believe a more correct solution, yet that requires a bit more work, is to actually parse your infix expression and build the binary expression tree out of it.

This shouldn't be all that hard since grammars for arithmetic expressions are defined all over the internet. After you've found a grammar that suits your needs, perform the parsing, build the tree, and when you have that you can get your postfix notation by performing a post-order traversal of the tree.

The Wikipedia article on binary expression trees may be a good place to start your documentation on this subject. Hope this helps!

Answer 2

The classic solution is Dijkstra's "Shunting Yard" algorithm: http://en.m.wikipedia.org/wiki/Shunting_yard_algorithm

Answer 3

use class Tools written by me

Tools.h

static class Tools
{
   public:
       static char* toPostfix(char* source);
       static double calculatePostfix(char* source);
       static bool contain(char* source,char character);
 };

Tools.cpp

#include "stdafx.h"
#include "Tools.h"
#include <stack>
#include <iostream>
#include <string>

using namespace std;

char* Tools::toPostfix(char* source)
{
    stack<char> symbol;
    string postfix = "";
    int i = 0;
    char variables[] = { "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" };
    bool find = false;

    while (*source != '\0')
    {
        switch (*source)
        {
        case '+':
        case '-':
        case '*':
        case '/':
            symbol.push(*source); 
            break;
        case ')':
            postfix += symbol.top();
            symbol.pop();
        default:
            find = Tools::contain(variables, *source);
            if (find)
            {
                 postfix += *source;
                 find = false;
             }

        }
        source++;
    }
    // attach other operator in stack(Pop All)
    while (!symbol.empty())
    {
         postfix += symbol.top();
         symbol.pop();
     }

     char* p = new char(postfix.length());
     const char* o = postfix.c_str();
     for (int i = 0; i < postfix.length(); i++)
         p[i] = o[i];
     return p;
}

double Tools::calculatePostfix(char* source)
{
    char numbers[] = { "0123456789" };
    stack<double> number;
    for (int i = 0; i < strlen(source); i++)
    {
        char character = source[i];
        if (Tools::contain(numbers, character))
        {
            number.push(atof(&character));
        }
        else
        {
            double number1, number2;
            switch (character)
            {
            case '+':
                number2 = number.top();
                number.pop();
                number1 = number.top();
                number.pop();
                number.push(number1 + number2);
                break;
            case '-':
                number2 = number.top();
                number.pop();
                number1 = number.top();
                number.pop();
                number.push(number1 - number2);
                break;
            case '*':
                number2 = number.top();
                number.pop();
                number1 = number.top();
                number.pop();
                number.push(number1 * number2);
                break;
            case '/':
                number2 = number.top();
                number.pop();
                number1 = number.top();
                number.pop();
                number.push(number1 / number2);
                break;
            }
        }
    }
    return number.top();
}

bool Tools::contain(char* source, char character)
{
    int size = strlen(source);
    for (int i = 0; i < size ; i++)
    {
        if (source[i] == character)
            return true;
    }
    return false;
}

usage :

 std::cout << "postFix : " << Tools::toPostfix("a+(b*c+t)") << std::endl;
 std::cout << "Answer : " << Tools::calculatePostfix("24*95+-") << std::endl;