Преобразование постфиксного инфикса в c ++ - PullRequest
Новая
       20

Преобразование постфиксного инфикса в c ++

0 голосов
/ 05 июля 2018

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

void calculator::convertInputIntoPostfix(){
  stack S;
  for(int i=0;i<mInfixInput.length();i++){
    if(mInfixInput[i]>='0' && mInfixInput[i]<='9'){
      mPostfixOutput+=mInfixInput[i];
    }
    else if(isOperator(mInfixInput[i])){                                                                                     
    while
    (!S.isEmpty()
    &&hasHigherPrecedenceThan(S.top(),mInfixInput[i])==true){
        mPostfixOutput += S.top();
        S.pop();
    }
    S.push(mInfixInput[i]);
    }
  }
  while(!S.isEmpty()){
    mPostfixOutput += S.top();
    S.pop();
 }                                                                                                                                                             
}

bool calculator::isOperator(int c) const
{
  return ((c == '+') ||
          (c == '-') ||
          (c == '*') ||
          (c == '/') ||
          (c == '^'));
}
bool calculator::hasHigherPrecedenceThan(int aLHS, int aRHS) const
{
  if ((aRHS == '+' || aRHS == '-') &&
      (aLHS == '*' || aLHS == '/' || aLHS == '^')) {
    return true;
  }
  if ((aRHS == '+' || aRHS == '-' || aRHS == '*' || aRHS == '/') &&
      (aLHS == '^')) {
    return true;
  }
  if (aLHS == '^' && aRHS == '^') {
    return true;
  }
  return false;
}

Случаи, не указанные выше (например, пробелы и запятые), можно игнорировать, а инфикс берется путем ввода в main. стек является стеком связанного списка. со значением, являющимся целым числом. выходные данные для 2 + 3 * 3 * 3 (желаемый ответ: 233 * 3 * +), которые я получаю, составляют 2333 ** +, поскольку он даже не входит в цикл while, который я написал, он просто хранит значения в стек и в конце выводит его.

1 Ответ

0 голосов
/ 05 июля 2018

2333**+ может быть неожиданным, но на самом деле это не так, просто неправильно ассоциируется.

То, как вы вычисляете приоритет, вы сообщаете алгоритму, что случай, когда aRHS == '*' && aLHS == '*' равен false, т.е. оператор не является левоассоциативным. Это. То же самое для всех остальных случаев, когда операторы равны, , кроме ^, которые вы ошибочно делаете левоассоциативными, когда они ассоциативно справа.

При определении приоритета в этом алгоритме принято использовать таблицу, а не цепочку if-else, и проверять наличие> =, а не> с точки зрения приоритета.

Версия алгоритма Dijkstra Shunting-yard, приведенная в Википедии, имеет это вместо вашего условия: 

while ((there is a function at the top of the operator stack)
    or (there is an operator at the top of the operator stack with greater precedence)
    or (the operator at the top of the operator stack has equal precedence and is left associative))
    and (the operator at the top of the operator stack is not a left bracket):
        pop operators from the operator stack onto the output queue.
...