Member Avatar for Der_sed

Can someone please suggest me a psuedo code to extract sub problems from an arithmetic expression:
For example,
How do I remove (8*2) and (3+2) from a given string (5 + 6(3+2) - 2(8*2) +1)

Input string will always start and end with paranthesis and the sub problems must be extracted as strings too.

string[] extract(string s1)
{
string extracted[]; 
if (s1[1]==')' )
cout<<"no expression"
return NULL

else

??????????



Return extracted[]
Edited by Der_sed because: n/a
  • 3 Contributors
  • 2 Replies
  • 98 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by WaltP

Dani AI

Generated

The simplest reliable approach is a single left-to-right scan with a stack of '(' positions. This exactly follows the idea from (track the most recent '(') and expands on by showing a safe way to both collect and remove matches without corrupting indices.

Use this plan:

  • Push index when you see '('.
  • On ')', pop the matching '(' index and record the pair (start,end) and the substring. That yields innermost parentheses first.
  • After the scan, either sort the extracted pairs by start if you want left-to-right order, or keep the LIFO order for innermost-first.
  • To remove those ranges from the original string safely, erase ranges from right-to-left (descending start), or build a new string skipping marked positions.

Example pseudocode (C++-style):

vector<pair<int,int>> ranges;
vector<string> extracted;
stack<int> st;
for (i = 0; i < s.size(); ++i) {
  if (s[i] == '(') st.push(i);
  else if (s[i] == ')') {
    if (st.empty()) handle_error_unmatched();
    j = st.top(); st.pop();
    ranges.push_back({j, i});
    extracted.push_back(s.substr(j, i - j + 1)); // include parentheses
  }
}
if (!st.empty()) handle_error_unmatched();
// optional: sort extracted by ranges[].first for left-to-right
// remove: sort ranges descending and erase or build a new string skipping ranges

Notes:

  • If you want the inner content without parentheses use substr(j+1, i-j-1).
  • Replacing with spaces (as suggested by ) works but can leave gaps; erasing or rebuilding is cleaner.
  • Time O(n), extra memory O(n). Handle empty or mismatched parentheses explicitly.

Recommended Answers

All 2 Replies

Member Avatar for Clinton Portis

In your example:

(5 + 6(3+2) - 2(8*2) +1)

Moving from left-to-right, in order to find a valid parenthesized pair, you have to find any condition where a ')' is found after traversing the most recent '('

From left-to-right, anytime multiple '(' are detected, the previous '(' position should be discarded.. only keep track of the position of the most current '('

Upon detection of the first ')', you now have the position of a valid parenthesized term. The parenthesis that make this term need to be discarded as candidates from future searches.

Edited by Clinton Portis because: n/a
Member Avatar for WaltP

As you loop through the equation, remember the position of each ( you see. When you see a ), extract everything between the ) and the last ( you saw. Replace these characters with SPACEs to clear out the extracted section. "Unremember" the ( location since it's no longer there. Continue through the equation until you reach the end.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.