fork download
copy 
  1. /* 
  2. ** Simon Nguyen
  3. ** CSCI 180 - David Letscher
  4. ** October 31, 2014
  5. */
  6.  
  7. #include <iostream>
  8. #include <string>
  9. using namespace std;
  10.  
  11. unsigned int lines;
  12. string inString, goalString;
  13.  
  14. /** Outputs, in sorted order, all solutions derivable from the given configuration */
  15. void solve(const string& goal,      // the goal string
  16.            const string& I,         // unused portion of "initial" string
  17.            const string& S,         // current stack sequence
  18.            const string& O,         // (partial) output string
  19.            const string& moves      // '++-+-' style trace of moves thus far
  20.           ) {
  21.  
  22. 	// Output the trace if it matches the goal string
  23. 	if (goal.size() == O.size()) {
  24. 		// cout << "Case 1\n";
  25. 		if (O == goal) {
  26. 			cout << moves << endl;
  27. 		}
  28.  
  29. 		return;
  30. 	}
  31.  
  32. 	// When beginning, push first character onto stack
  33. 	if (S.empty() && O.empty()) {
  34. 		// cout << "Case 2\n";
  35. 		string tempI = I;
  36. 		string tempS = S;
  37. 		string tempM = moves;
  38.  
  39. 		tempI.erase(0, 1);
  40. 		tempS += I[0];
  41. 		tempM += "+";
  42.  
  43. 		// cout << tempI << " " << tempS << " " << tempM << endl;
  44.  
  45. 		solve(goal, tempI, tempS, O, tempM);
  46. 		return;
  47. 	}
  48.  
  49. 	// Push onto stack S if string I is not empty
  50. 	if (!I.empty()) {
  51. 		// cout << "Case 3\n";
  52. 		string tempI = I;
  53. 		string tempS = S;
  54. 		string tempM = moves;
  55.  
  56. 		tempS += tempI[0];
  57. 		tempI.erase(0, 1);
  58. 		tempM += "+";
  59.  
  60. 		// cout << tempI << " " << tempS << " " << tempM << endl;
  61.  
  62. 		solve(goal, tempI, tempS, O, tempM);
  63. 	}
  64.  
  65. 	// Pop off I onto S
  66. 	if (!S.empty()) {
  67. 		// cout << "Case 4\n";
  68. 		string tempS = S;
  69. 		string tempO = O;
  70. 		string tempM = moves;
  71.  
  72. 		tempO += S.back();
  73. 		tempS.erase(tempS.length() - 1);
  74. 		tempM += "-";
  75.  
  76. 		// cout << tempS << " " << tempO << " " << tempM << endl;
  77.  
  78. 		solve(goal, I, tempS, tempO, tempM);
  79. 	}
  80. }
  81.  
  82. int main() {
  83.  
  84. 	cin >> lines;
  85.  
  86. 	// Run until an input of 0 is given
  87. 	for(unsigned int i; i < lines; i++) {
  88. 		cin >> inString >> goalString;
  89.  
  90. 		cout << "Output for " << inString << " " << goalString << endl;
  91. 		cout << "[" << endl;
  92. 		solve(goalString, inString, "", "", "");
  93. 		cout << "]" << endl;
  94. 	}
  95.  
  96. 	return 0;
  97. }
  98.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
4
abc bac
abc cab
aab aba
eeep epee
stdout
copy 
Output for abc bac
[
++--+-
]
Output for abc cab
[
]
Output for aab aba
[
++-+--
+-++--
]
Output for eeep epee
[
+++-+---
++-++---
+-+++---
]
https://ideone.com/8JTPd6
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!