Infix to prefix parenthesis

Question

How would I convert this to where it accepts parenthesis, currently the only thing you can use is like 2 + 4 * 7. i'm having trouble figuring out how to ignore the parenthesis so something like (2 + 3) * 7 would read out * + 2 3 7. anything helps thanks.

#include <iostream>
#include <sstream>
#include <stack>
#include <limits>
#include <string>
using namespace std;

int priority(char a)
{
    int temp;

    if (a == '*' || a == '/' || a == '%')
       temp = 2;
    else  if (a == '+' || a == '-')
       temp = 1;
    return temp;
}

//start
int main()
{
    //declare a string called "infix"
    string infix;
    stringstream output;
    stack<char> s1, s2;

    cout << "Enter an arithmetic expression with no perenthesis: " << endl;
    getline(cin, infix);

    //this loops through backwards searching for the operators 
    for(int i = infix.length() - 1; i >= 0; i--)
    {
        //check the input against +,-,/,*,%
        if (infix[i] == '+' || infix[i] == '-' || 
            infix[i] == '*' || infix[i] == '/' || infix[i] == '%')
        {
            while(!s1.empty() && priority(s1.top()) > priority(infix[i]))
            {       
                output << s1.top();
                s2.push(s1.top());
                s1.pop();           
            }

            s1.push(infix[i]);
        }
        // I think i need to add an else if to check for parenthesis
        // not sure how
        else
        {   
            output << infix[i];
            s2.push(infix[i]);
        }
    }

    while(!s1.empty())
    {
        output << s1.top();
        s2.push(s1.top());
        s1.pop();
    }

    cout << "\nAnswer: ";

    while(!s2.empty())
    {
        cout << s2.top();
        s2.pop();
    }

    cout <<"\n\nPress enter to exit" << endl;
}

Answer 1

As you pointed out you intend to convert from infix to prefix notation. Unfortunately your quest won't be as easy as just skipping some parentheses.

In contrast to prefix notation that can cope without parentheses infix notation requires them to arbitrarily describe any possible calculation you want to perform.

Take this for an example:

(1 + 2) / (3 + 4)

while this can be pretty well written down as

 / + 1 2 + 3 4

in prefix notation you won't find any way to express the same calculation in infix notation without any parentheses.

Instead of trying to sequentially analyze every one operation after the other the will need a full blown parser building a parse tree of your string in infix notation.

Otherwise there is no chance to get the calculation right. Think about something like

  (1 + 2 * ( 3 / (4 + 3) * 48 + (81 / 4)) + 8) - 9

for example.

The term related to your question, that you might want to investigate upon is usually called expression grammar.

Take a look here for example: (see: http://en.wikipedia.org/wiki/Parsing_expression_grammar)

Answer 2

You are looking for reverse polish notation

Here is a reference - http://en.wikipedia.org/wiki/Reverse_polish_notation

You can get links and reading material to implement it.

BTW - Do not do it in 6502 assembler - it is a nightmare!