17번째 줄에서 매 반복마다 input.length()를 호출합니다. 문자열의 길이를 구하는 데에는 길이에 비례하는 시간이 걸립니다. int len=input.length() 등으로 길이를 미리 구해놓으시는 걸 추천합니다.

위에분이 언급하신 내용은 다른언어는 모르겠지만, 자바와는 관련 없는 내용입니다. (https://stackoverflow.com/questions/20264227/what-is-complexity-of-length-function-in-string-class-of-java?rq=1)

하지만 특별한 이유가 없는 이상 저도 변수로 따로 빼서 구하시는 것을 추천드립니다. 우선 해당 문제 시간 제한이 0.3 인데.. 너무 비효율적인 코드가 많이 보여서 조금 최적화를 해야 할 것같습니다.

(로직쪽은 건들지 않겠습니다.. 크게 틀린점은 안보이기도하구요)

우선 입력도 긴 편이기 때문에 Scanner 보다 BufferedReader 추천드리고, split 보다 StringTokenizer로.. 

하나하나 다 설명드리기엔 저도 부족한점이 있고 해서  꼭 검색 해보시길 바랍니다. 무조건 후자를 써야한다는 것은 아닙니다.

각각 다른 점이 조금 있어 필요한 상황에 맞춰 쓰시면 됩니다. (우선 후자가 성능상으론 더 빠르다고 이해하시면 될 것 같습니다.)

그리고 자바에서 문자열 처리는 웬만하면 피하시는게 좋습니다.. 아 쓰다보니까 너무 많은데.. 문자열은 String pool 관련해서 꼭 찾아보시길 바랍니다!

그리고 결정적으로.. toString 메소드는 19번째줄에 있잖아요. 저 메소드는 전에 열어봤을땐 내부에 반복문이 붙어있었는데.. 아마 그문제가 아닌가 싶습니다.

질문자님 코드 기준으로 제가 다시 코드를 정리해봤습니다.

12번쨰 줄은 br.readLine()으로 한줄을 문자열로 받습니다.(공백, 숫자 구분없이 모두 문자열로 한줄로 붙여받는 작업입니다.)

그리고 받은 값을 toCharArray로 하나씩 캐릭터로 바꾸어 char 배열에 담아줍니다. 해당 메소드도 문자열 길이만큼 반복문이 내부에 돌겁니다.

스택의 자료형을 문자열에서 char로 변경했구요 그에 맞춰서 입력 처리해줬습니다..

그리고 StringTokenizer 통해 들어오는 cmd 들을 space 기준으로 쪼개줍니다. 받은 입력을 통해 결과값이 처리되어나오겠죠..

코드는 아래와 같습니다. 일단 시간초과는 피할 수 있을것 같습니다.

대부분 새로 고쳤는데 차이점을 보셔야 할 부분은 주석처리로 해봤습니다.

입력에 대한 처리만 고쳐드렸는데요.. 되도록이면 코드 자체는 안건드리는데, 하나하나 써드리다보니.. 거의 제가 다 쓰는 상황이 오더라구요.

모르는 부분에 대해선 댓글 달아주세요. 내부적으로 자세히 설명은 못드려도 어떻게 동작하는지 정도는 말씀드릴 수 있습니다.

대부분 아실만한 메소드라 생각되는데 혹시 모르시는거 있으면 꼭 찾아보세요~