C++: нумеруем скобки в строке

Ещё одна "скобочная" задача, каковые хорошо применять при изучении синтаксического разбора строк.

Имеется выражение exp длиной n символов, содержащее круглые скобки. Вывести номера скобок в выражении, то есть:

(a+(b/c))-(d*e+(1-f))(();
1  2   21 3    4   43566

Использован стандартный стек, проверено в консоли Visual Studio 2015, трудоёмкость алгоритма равна O(n).

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;

void bracketNumbers(string exp, int n) {
 int leftNumber = 1;
 stack <int> rightNumber;
 for (int i = 0; i < n; i++) {
  if (exp[i] == '(') {
   cout << leftNumber;
   rightNumber.push(leftNumber);
   leftNumber++;
  }
  else if (exp[i] == ')') {
   cout << rightNumber.top();
   if (rightNumber.size()>1) //Убрать условие, если скобки обязаны быть парными
    rightNumber.pop();
  }
  else cout << " ";
 }
}

int main() {
 string exp = "(a+(b/c))-(d*e+(1-f))(();";
 cout << exp << endl;
 bracketNumbers(exp, exp.size());
 cin.get(); return 0;
}

28.02.2018, 13:15 [1896 просмотров]