CareerCup

by using stack, we can check whether parenthesis are matched or not. Same algo we can use to check the above valid math expression.

Does any one has idea to solve short cut expression problems.

e.g :: (a+ (b+=c)) // valid
(a+(b=+c)) // invalid

I wrote the following pseudo-code:

for each character in the string 
 		push onto a stack, keeping track of the braces that are being used.
 		if you encounter any non-numeric characters, braces, or operands, return false 
 		if you encounter a closing brace that has NOT has an opening brace, return false
 		if you encounter an opening brace following by an operand, return false
 		if you encounter a closing brace, pop off all values off the stack (until you reach opening)
			if there is an operand by the closing brace, return false
 			if there is nothing between the opening & closing brace, return false
 			if you encounter two operands in a row, return false
 			once you pop off the opening brace, pop in any number.

package mytest;

import java.util.Stack;

/**
 *
 * @author Sun
 */
public class MyTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        String test="12*9-[(66+11)]*(77-22)";
        System.out.println("Test equation: "+test);
        System.out.println("Valid ? "+checkValid(test.toCharArray()));
    }
    static boolean checkValid(char[] equ){
        int i,j=equ.length;
        Stack<Character> astack=new Stack<>();
        if(j==0)return false;

        for(i=0;i<j;i++){
                   // System.out.println("?"+equ[i]);
            if(isOpen(equ[i])){
                if(!astack.isEmpty() && isNumber(astack.peek())){
                    return false;
                }
                astack.push(equ[i]);
            }else if(isNumber(equ[i])){
                astack.push(equ[i]);
            }else if(isOp(equ[i])){
                if(astack.isEmpty() || !isNumber(astack.peek())){
                    return false;
                }
                astack.push(equ[i]);
            }else if(isClose(equ[i])){
                if(astack.isEmpty() || !isNumber(astack.peek())){
                    return false;
                }
                while(!astack.isEmpty()){
                    char temp=astack.pop();
                    if(isOpen(temp)){
                        if(doMatch(temp,equ[i])){
                            break;
                        }else{
                            return false;//unexpected open
                        }
                    }else{
                        if(astack.isEmpty()){
                            return false;
                        }
                    }
                }
                astack.push('1');
            }else{ //unexpected char
                return false;
            }
        }
        if(!astack.isEmpty() && !isNumber(astack.peek())) {
            return false;
        }
        while(!astack.isEmpty()){
            if(isOpen(astack.pop()))return false;
        }
         
        return true;
    }

    private static boolean isOpen(char c) {
        if(c=='(' || c=='[')return true;
        return false;
    }

    private static boolean isNumber(char c) {
        if(c>='0' && c<='9')return true;
        return false;
    }

    private static boolean isOp(char c) {
        if(c=='+' || c=='-' || c=='*' || c=='/')return true;
        return false;
    }

    private static boolean isClose(char c) {
        if(c==')' || c==']')return true;
        return false;
    }

    private static boolean doMatch(char temp, char c) {
        if((temp=='(' && c==')')||(temp=='[' && c==']'))return true;
        return false;
    }

}

I solved this using C++ in my blog - addaxsoft.com/?p=58

Can anyone help me to solve this using vb script please...

take 3 variables for each type of brackets initialize to 0, for open one do ++ for close one do -- and whenever the value become negative. Not a possible expression, and also after every operator there should not be an operator. after the end of expression check each variable is zero.