Раздел «Образование».FIVTLecturesTerm2Lecture06:
<<Лекции ФИВТ, 2-й семестр

Лекция 4. Перевод из постфиксной в инфиксную нотацию, линейный алгоритм.

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

Реализация, основанная на конкатенации строк (string)

#include <list>
#include <string>
#include <iostream>

using namespace std;
int main() {
  list< string >  stack;
  string str;
  while (cin >> str) {
    if (str == "+" || str == "-" || str == "*" || str == "/" ) {
      string b = stack.back(); stack.pop_back();
      string a = stack.back(); stack.pop_back();
      stack.push_back( string("(") + a + str + b + ")");
    } else {
      stack.push_back( str );
    }
  }

  cout << *stack.rbegin();
  return 0;
}

Реализация, основанная на списках строк и слиянии списков строк list

#include <list>
#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>

using namespace std;
int main() {
  list< list<string> >  stack;
  string str;
  while (cin >> str) {
    if (str == "+" || str == "*") {
      list<string> b = stack.back(); stack.pop_back();
      list<string> a = stack.back();
      a.push_front("(");
      a.push_back(str);
      a.splice(a.end(), b);
      a.push_back(")");
    } else {
      list<string> a
      a.push_back(str);
      stack.push_back( a );
    }
  }

  list<string> result = stack.front();
  stack.pop_front();
  
  copy(result.begin(), result.end(), ostream_iterator<string>(cout, ""));
  
  /* Одна строка выше эквивалентна четырём следующим строкам:
  list::iterator it;
  for(it = result->begin(); it != result->end(); it++) {
    cout << *it;
  }
  */

  cout << endl;
  
  return 0;
}

Тестирование функциональности

Пусть исполняемая программа имеет имя a.out. Приведём команды, позволяющие протестировать её работу.

$ cat > in1.txt
1 2 +
$ cat > correct_out1.txt.txt
(1+2)
$ cat > in2.txt
1 2 + 3 4 + *
$ cat > correct_out2.txt.txt
(1+2)*(3+4)

Вбейте самостоятельно 8 других тестовых входных данных и правильные ответы для них.

# команда для запуска 10 тестов;
# в текущей директории должны быть файлы in1.txt correct_out1.txt in2.txt correct_out2.txt ...
# выводятся результаты выполнения программы на 10 входных данных
for((i=1; $i <= 10; i++)); do ./a.out < in$i.txt; done

# команда для проверки простых 10 тестов;
# в текущей директории должны быть файлы in1.txt correct_out1.txt in2.txt correct_out2.txt ...
# для каждого теста выводится ok или wrong в зависимости от того, 
# совпадает ли вывод программы с правильным ответом
for((i=1; $i <= 10; i++)); do  
./a.out < in$i.txt > out$i.txt; 
if [ `diff out$i.txt correct_out$i.txt` eq ""]; 
then 
echo "$i: ok"; 
else 
echo "$i: wrong"; 
fi;  
done

Тестирование производительности

# команда для проверки выражения вида  1 1 + 1 + 1 + 1 +
$ (echo 1; for((i=1; $i <= 3000; i++)); do echo "1 +";  done) | (time ./a.out) > result.txt

# команда для проверки выражения вида  1 1 1 1 1 1 + + + + +
n=3000; (
for((i=1; $i <= $n; i++)); do echo "1 ";  done; 
for((i=1; $i < $n; i++)); do echo "+ ";  done; 
) | (time ./a.out) > result.txt

Если n заменить на 6000, то увидим, что время работы в среднем увеличивается не в 2, а в 4 раза. Проведя ряд экспериментов для разных n, можно увидеть, что обе реализации работают квадратичное время.

Правильная релизация

Приведённая ниже реализация работает линейное время от размера входа.

#include <list>
#include <string>
#include <iterator>
#include <iostream>

using namespace std;
int main() {
  list< list<string>*  >  stack;
  string str;
  while (cin >> str) {
    if (str == "+" || str == "*") {
      list<string> *b = stack.back(); stack.pop_back();
      list<string> *a = stack.back();
      a->push_front("(");
      a->push_back(str);
      a->splice(a->end(), *b);
      a->push_back(")");
      delete b;
    } else {
      list<string> *a = new list<string>();
      a->push_back(str);
      stack.push_back( a );
    }
  }

  list<string> *result = stack.front();
  stack.pop_front();
  
  copy(result->begin(), result->end(), ostream_iterator<string>(cout, ""));

  cout << endl;

  delete result;

  return 0;
}

Вопросы и задачи:

-- ArtemVoroztsov - 09 Mar 2010