Инфикс для префиксной скобки

Как бы мне преобразовать это туда, где оно принимает круглые скобки, в настоящее время единственное, что вы можете использовать, это как 2 + 4 * 7. Мне трудно понять, как игнорировать круглые скобки, чтобы что-то вроде (2 + 3) * 7 читалось out * + 2 3 7. спасибо, что-нибудь поможет.

#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;
}

person user2206227    schedule 29.03.2013    source источник


Ответы (2)


Вы ищете обратную польскую нотацию

Вот ссылка - http://en.wikipedia.org/wiki/Reverse_polish_notation

Вы можете получить ссылки и материалы для чтения, чтобы реализовать его.

Кстати - Не делайте этого на ассемблере 6502 - это кошмар!

person Ed Heal    schedule 29.03.2013

Как вы указали, вы намерены преобразовать нотацию infix в prefix. К сожалению, ваш квест не будет таким простым, как просто пропустить некоторые скобки.

В отличие от префиксной нотации, которая может обходиться без круглых скобок, инфиксная нотация требует от них произвольного описания любых возможных вычислений, которые вы хотите выполнить.

Возьмите это для примера:

(1 + 2) / (3 + 4)

в то время как это может быть довольно хорошо записано как

 / + 1 2 + 3 4

в префиксной нотации вы не найдете способа выразить то же самое вычисление в инфиксной нотации без каких-либо круглых скобок.

Вместо того, чтобы пытаться последовательно анализировать каждую операцию за другой, вам понадобится полноценный синтаксический анализатор, создающий дерево синтаксического анализа вашей строки в инфиксной нотации.

В противном случае нет никаких шансов получить правильный расчет. Подумайте о чем-то вроде

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

Например.

Термин, связанный с вашим вопросом, который вы, возможно, захотите исследовать, обычно называется грамматика выражений.

Взгляните сюда, например: (см.: http://en.wikipedia.org/wiki/Parsing_expression_grammar)

person mikyra    schedule 29.03.2013