Инфиксная, префиксная и постфиксная формы записи выражений

Для записи выражений при их программном оценивании часто используются не только привычная нам запись вида (A+B)/(C*D)-E/F, называемая инфиксной, но и постфиксная (была у меня когда-то в МК-61), и префиксная формы записи выражений.

Ниже показан простой конвертер выражения, записанного в постфиксной форме, в префиксную и инфиксную формы. Предполагается, что выражение в постфиксной форме корректно и состоит только их однобуквенных латинских операндов (переменных) A..Z и 4 знаков арифметических действий.

Для работы применяется стандартный стек, программка проверена в консоли Visual Studio 2015, на примере из "Вики" сработала :)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isOperand(char x) { //Да, если буква (операнд)
 return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z');
}

bool isOperator(char x) { //Да, если разрешённый оператор (арифметическое действие)
 switch (x) {
 case '+': case '-': case '/': case '*':  return true;
 }
 return false;
}

string getInfixFromPostfix(string exp) { //Получить инфиксную запись по постфиксной
 stack <string> s;
 for (int i = 0; exp[i] != '\0'; i++) {
  if (isOperand(exp[i])) { //Операнды - в стек
   string op(1, exp[i]);
   s.push(op);
  }
  else {
   string op1 = s.top();
   s.pop();
   string op2 = s.top();
   s.pop();
   s.push("(" + op2 + exp[i] + op1 + ")");
  }
 }
 return s.top(); //В стеке должен остаться 1 элемент, содержащий инфиксную запись
}

string getPrefixFromPostfix(string post_exp) { //Получить префиксную запись по постфиксной
 stack <string> s;
 size_t length = post_exp.size();
 for (size_t i = 0; i < length; i++) {
  if (isOperator(post_exp[i])) {
   string op1 = s.top();
   s.pop();
   string op2 = s.top();
   s.pop();
   string temp = post_exp[i] + op2 + op1;
   s.push(temp);
  }
  else {
   s.push(string(1, post_exp[i]));
  }
 }
 string ans = "";
 while (!s.empty()) {
  ans += s.top();
  s.pop();
 }
 return ans;
}

int main() {
 string exp = "CDB*AE-B^/+";
 //Предполагаем, что постфиксная запись корректна и нет лишних пробелов в строке!
 cout << endl << "Postfix:" << exp;
 cout << endl << "Prefix:" << getPrefixFromPostfix(exp);
 cout << endl << "Infix:" << getInfixFromPostfix(exp);
 cin.get(); return 0;
}

28.02.2018, 14:19 [5462 просмотра]