现在的位置: 首页 > 综合 > 正文

11 栈与编译器(二):括号匹配

2013年04月25日 ⁄ 综合 ⁄ 共 2961字 ⁄ 字号 评论关闭

文本中遇到左括号入栈,遇到右括号则查栈顶是否匹配并弹出,直到结束。

package nuaa.ds;

import java.io.IOException;
import java.io.PushbackReader;
import java.io.Reader;

/**
 * 扫描输入流,生成需要的识别的标记序列
 * @author Administrator
 *
 */
public class Tokenizer {
	public static final int SLASH_SLASH = 0;
	public static final int SLASH_STAR = 1;
	private PushbackReader in; //input stream
	private char ch;  //current character
	private int currentLine; // current line
	private int errors; //number of errors seen
	public Tokenizer(Reader inStream){
		errors = 0;
		ch = '\0';
		currentLine = 1;
		in = new PushbackReader(inStream);
	}
	
	public int getLineNumber(){
		return currentLine;
	}
	
	public int getErrorCount(){
		return errors;
	}
	
	//处理注释、处理引号、遇到括号则返回
	public char getNextOpenClose(){
		while(nextChar()){
			if(ch=='/')
				processSlash();
			else if(ch=='\''||ch=='"')
				skipQuote(ch);
			else if(ch=='('||ch=='['||ch=='{'||
						ch==')'||ch==']'||ch=='}')
				return ch;
		}
		return '\0';
	}
	
	
	private boolean nextChar(){
		try{
			int readVal = in.read();
			if(readVal==-1)
				return false;
			ch = (char)readVal;
			if(ch=='\n')
				currentLine++;
			return true;
		}catch(IOException e){
			return false;
		}
	}
	private void putBackChar(){
		if(ch=='\n')
			currentLine--;
		try{
			in.unread((int)ch);
		}catch(IOException e){}
	}
	
	
	private void skipComment(int start){
		if(start==SLASH_SLASH){
			//nextChar直接读到文件尾,返回false
			//不在文件尾,必然有换行符 
			while(nextChar()&&(ch!='\n'))
				;
			return;
		}
		
		//寻找*/字符串,代码有点问题,要求出现*一定要接/
		boolean state = false;
		while(nextChar()){
			if(state&&ch=='/')
				return;
			state = (ch=='*');
		}
		errors++;
		System.out.println("Unterminated comment!");
	}
	private void skipQuote(char quoteType){
		while(nextChar()){
			if(ch==quoteType)
				return;
			if(ch=='\n'){
				errors++;
				System.out.println("Missing closed quote at line "+currentLine);
				return;
			}else if(ch=='\\')
				nextChar();
		}
	}
	private void processSlash(){
		if(nextChar()){
			if(ch=='*'){
				if(nextChar()&&ch!='*'){//javadoc comment
					putBackChar();
				}
				skipComment(SLASH_STAR);
			}else if(ch=='/')
				skipComment(SLASH_SLASH);
			else if(ch!='\n')
				putBackChar();
		}
	}

}

package nuaa.ds;

import java.io.Reader;
import java.util.Stack;

public class Balance {
	private Tokenizer tok;
	private int errors;
	public Balance(Reader inStream){
		errors = 0;
		tok = new Tokenizer(inStream);
	}
	

	public int checkBalance(){
		char ch;
		Symbol match = null;
		Stack<Symbol> pendingTokens = new Stack<Symbol>();
		while((ch=tok.getNextOpenClose())!='\0'){//\0是函数最后的返回值
			Symbol lastSymbol = new Symbol(ch,tok.getLineNumber());
			switch(ch){
			case '(':case'[':case '{':
				pendingTokens.push(lastSymbol);
				break;
			case ')':case ']':case '}':
				if(pendingTokens.isEmpty()){
					errors++;
					System.out.println("Extraneous "+ch+" at line "+
													tok.getLineNumber());
				}else{
					match = pendingTokens.pop();
					checkMatch(match,lastSymbol);
				}
			}
		}
		
		while(!pendingTokens.isEmpty()){
			match = pendingTokens.pop();
			System.out.println("Unmatched "+match.token+
									" at line "+match.theLine);
			errors++;
		}
		return errors+tok.getErrorCount();
	}
	
	private void checkMatch(Symbol opSym,Symbol clSym){
		if(opSym.token=='('&&clSym.token!=')'||
				opSym.token=='['&&clSym.token!=']'||
				opSym.token=='{'&&clSym.token!='}'){
			System.out.println("Found "+clSym.token+" on line "+
									tok.getLineNumber()+"; dose not match "
										+opSym.token+" at line "+opSym.theLine);
			errors++;
		}
	}
	
	private static class Symbol{
		public char token;
		public int theLine;
		
		public Symbol(char tok,int line){
			token = tok;
			theLine = line;
		}
	}
}

抱歉!评论已关闭.