Removal of redundant expression inside ()

2010-05-31  来源:本站原创  分类:Tech  人气:284 

This is a long time ago a friend asked me CSDN's a question:

Removal of redundant expression inside ()
Check whether the string matches the expression in parentheses;
The number of left parentheses is not equal with the number in brackets shall be no match;
Remove the extra left bracket or right bracket, the priority appears to retain the first bracket;
Matching parentheses after the removal of invalid: such as: ((expression)) should be (expression);
Consider only small brackets, do not appear to consider the first case the right parenthesis;
Required to achieve the function: (string up to length 60; expression need not consider the correctness)
void Bracket (char * src, char * dst);

If the match is output through the original string dst;

If you do not place more than match the brackets under requirements adopted after the dst string after the output matching

Example input: 12 + (345 * 25-34) output: 12 + (345 * 25-34)

Enter: 12 + (345 * (25-34) output: 12 + (345 * 25-34)

Input: (12 +345) * 25) -34 Output: (12 +345) * 25-34

Enter: (543 + (256-43) * 203)) +24 Output: (543 + (256-43) * 203) +24

Input: ((1 +2) * ((34-2 ))+(( 2 * 8-1) Output: ((1 +2) * (34-2) +2 * 8-1)

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#define maxv(a, b) ((a) >= (b) ? (a) : (b))
#define minv(a, b) ((a) <= (b) ? (a) : (b))
#define MAX_N 60
using namespace std;
bool unValid[MAX_N + 1];
char input[MAX_N + 1];
char output[MAX_N + 1];
int len;
int lp[MAX_N + 1];
int rp[MAX_N + 1];
struct para
{
        char type;
        int pos;
        para(char t, int p)
        {
                type = t;
                pos = p;
        }
};
stack<para> pStack;
void Bracket(char* src, char* dst)
{
        int i;
        // Extraneous closing parenthesis
        if(lp[0] < rp[0])
        {
                for(i = rp[0]; i >= lp[0] + 1; i--)
                {
                        unValid[rp] = true;
                        rp = -1;
                }
        }
        // Extraneous left parenthesis
        else if(lp[0] > rp[0])
        {
                for(i = lp[0]; i >= rp[0] + 1; i--)
                {
                        unValid[lp] = true;
                        lp = -1;
                }
        }
        // Matching parentheses after removing invalid  : If  :(( Expression  ))  Should be  ( Expression  )
        for(i = 0; i < len; i++)
        {
                if(input == '(' && !unValid)
                {
                        while(pStack.size() >= 1 && pStack.top().type == ')')
                                pStack.pop();
                        pStack.push(para('(', i));
                }
                else if(input == ')' && !unValid)
                {
                        if(pStack.size() >= 3)
                        {
                                para p1 = pStack.top();
                                if(p1.type == ')')
                                {
                                        pStack.pop();
                                        para p2 = pStack.top();
                                        pStack.pop();
                                        para p3 = pStack.top();
                                        pStack.pop();
                                        if(p1.type == ')' && p2.type == '(' && p3.type == '(' && p2.pos - p3.pos == 1 && i - p1.pos == 1)
                                        {
                                                unValid[p1.pos] = true;
                                                unValid[p2.pos] = true;
                                        }
                                        pStack.push(p3);
                                }
                        }
                        pStack.push(para(')', i));
                }
        }

        int k = 0;
        for(i = 0; i < len; i++)
        {
                if(!unValid)
                {
                        dst[k++] = input;
                }
        }
        dst[k] = '\0';
}
int main()
{
        char ch;
        while((ch = getchar()) != 10)
        {
                input[len++] = ch;
                if(ch == '(')
                {
                        lp[0]++;
                        lp[lp[0]] = len - 1;
                }
                else if(ch == ')')
                {
                        rp[0]++;
                        rp[rp[0]] = len - 1;
                }
        }
        Bracket(input, output);
        printf("%s\n", output);
        return 0;
}
相关文章
  • Removal of redundant expression inside () 2010-05-31

    This is a long time ago a friend asked me CSDN's a question: Removal of redundant expression inside () Check whether the string matches the expression in parentheses; The number of left parentheses is not equal with the number in brackets shall be no

  • java programming regular expression inside 2010-06-15

    In my work which, generally regular expression java application, are two: # 1 according to the given string matches the format to see if satisfied overall style. Syntax is very familiar: textInput.matches ("regex") Note: .*? That lazy match, tha

  • Java filter regular expression special characters reserved ---- 2010-04-22

    / / Filter special characters public static String StringFilter (String str) throws PatternSyntaxException ( / / Allow only letters and numbers / / String regEx = "[^ a-zA-Z0-9]"; / / Clear out all the special characters String regEx ="[`~!

  • android regular expression 2010-06-12

    editText the use of regular expression rules check whether the input import android.app.Activity; import android.os.Bundle; import android.view.View; import android.widget.Button; import android.widget.EditText; / ** * Class which shows how to valida

  • java regular expression entry 2010-08-26

    <Type = "text / javascript"> As we all know, in the program development, will inevitably face need to match, find, replace, determine string to happen, but these sometimes complicated, if the pure coding solution, often would be a waste of

  • JS common statement 2009-05-28

    1.document.write ( ""); output statement Notes for the 2.JS / / 3. The traditional sequence of HTML documents are: document-> html-> (head, body) 4. A browser window in order DOM are: window-> (navigator, screen, history, location, docu

  • User has a good summary of "JS grammar dictionary" 2009-08-27

    Output statement 1.document.write (""); Notes for the 2.JS / / 3. The traditional order of the HTML document: document-> html-> (head, body) 4. A browser window DOM is the order of: window-> (navigator, screen, history, location, docume

  • 107 commonly used Javascript statement 2009-09-17

    1. Document.write ( ""); output statement Notes for the 2.JS / / 3. The traditional order of the HTML document: document-> html-> (head, body) 4. A browser window DOM is the order of: window-> (navigator, screen, history, location, docu

  • java regular expressions 2010-03-29

    We all know, in the program development, will inevitably encounter the need match, find, replace, to determine the string to happen, but sometimes these situations more complex, if the pure coding solution, often a waste of programmer time and effort

  • JSTL use of small technology 2010-03-29

    JSTL collection action on the Map 1, iteration When the forEach attribute of the items in the expression of the value of java.util.Map, then the variable named var is the type of java.util.Map.Entry. Then var = entry, then use the expression $ (entry

  • jquery refresh the page-based approach, and some javascript functions 2008-06-07

    jquery refresh the page partial refresh: This method more to go, and often there are several; $. get method, $. post method, $. getJson method, $. ajax as follows The first two use basically the same $. get ( "Default.php", (id: "1", p

  • 107 Common Javascript statement 2009-11-13

    1. Document.write ( ""); Output Statement 2.JS the comment is / / 3. The traditional sequence of HTML documents: document-> html-> (head, body) 4. A browser window in the DOM order is: window-> (navigator, screen, history, location, doc

  • javascript Collection study notes 107 2009-10-05

    js Collection study notes, record the contents of the JAVA SCRIPT Collection 1.document.write (""); Output Statement 2.JS in the comments for / / 3. The traditional sequence of HTML documents: document-> html-> (head, body) 4. A browser wi

  • JavaScript-based (change) 2009-03-28

    1.document.write (""); for the output statement 2.JS in the comments for / / 3. The traditional sequence of HTML documents: document-> html-> (head, body) 4. A browser window in the DOM order is: window-> (navigator, screen, history, lo

  • JavaScript Fundamentals (change) 2010-03-16

    1.document.write (""); for the output statement 2.JS the comment is / / 3. The traditional HTML document order is: document-> html-> (head, body) 4. A browser window in the DOM order is: window-> (navigator, screen, history, location, d

  • Fixed point and floating-point 2010-02-21

    Decimal representation To save memory, the computer numerical data of the decimal point position is implied, and the location of the decimal point may be either fixed, it can be change. Fixed point and floating-point If the position of the decimal po

  • 107 Useful tips javascript 2010-04-02

    1.document.write (""); output statements 2.JS the comment is / / 3. The traditional HTML document order is: document-> html-> (head, body) 4. A browser window in the DOM order is: window-> (navigator, screen, history, location, document

  • Use ImageMagick for your website weight loss 2010-03-20

    Images as a percentage of page weight for the Alexa top 10 global web sites Share pictures on the site more and more important. Better optimization of images can improve the website speed. Reduce the broadband traffic. 1. On the users to upload pictu

  • More than 100 useful JavaScript functions and a large collection of basic written 2010-04-15

    1.document.write(""); The output statement 2.JS Comments in the // 3. The traditional order of HTML documents :document->html->(head,body) 4. A browser window in the DOM order is :window->(navigator,screen,history,location,document) 5.

  • JS built-in function (transfer) 2010-04-19

    1.document.write (""); output statements 2.JS the comment is / / 3. The traditional sequence of HTML documents are: document-> html-> (head, body) 4. A browser window in the DOM order is: window-> (navigator, screen, history, location,