sumanth232
BAN USERConvert the given infix expression ("3+12*3-4/7") to postfix (3 12 3 * + 4 7 / -).
Here is the algorithm and code to do so http://geeksquiz.com/stack-set-2-infix-to-postfix/
The postfix expressions can be evaluated very easily using a stack
we can modify the longest_common_subsequence(a, a) to find the value of the longest repeated subsequence in a by excluding the cases when i == j, (which we know are always equal in this case). Here is the code in C++
int LongestRepeatedSubsequence(char* a, char* b) {
int n = strlen(a), m = strlen(b);
int len[n+1][m+1] // should be dynamically allotted and freed
for(int i = 0; i < (n+1); ++i) {
for(int j = 0; j < (m+1); ++j) {
if(i==0 || j==0) len[i][j] = 0;
else {
if(a[i-1] == b[j-1] && i-1!=j-1) len[i][j] = 1 + len[i-1][j-1];
else len[i][j] = max(len[i-1][j], len[i][j-1]);
}
}
}
return len[n][m];
}
int main(int argc, char const *argv[])
{
char* str[] = {"abab", "abba", "acbdaghccfbc", "abcdacb"};
for(int i = 0; i < (int(sizeof(str)/sizeof(str[0]))); ++i) {
printf("%s - LRS = %d\n",str[i], LongestRepeatedSubsequence(str[i], str[i]) );
}
return 0;
}
it should be
str[i] = '\0';
This has to be a doubly linked list, for the removal of nodes to be O(1) , right ?
- sumanth232 October 13, 2015