实验三-逆波兰表达式的产生及计算

江苏科技大学 计算机学院 编译原理实验报告0941901228 章进兴实验三 逆波兰表达式的产生及计算一、实验目的 非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。三、逆波兰表达式的产生及计算实验设计思想及算法u 逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。u 产生逆波兰式的前提 中缀算术表达式u 逆波兰式生成的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。运用以上算法分析表达式(a+b*c)*d的过程如下：当前符号输入区符号栈输出区（ a+b*c)*da +b*c)*d(+ *c)*d(ab c)*d(+a* )*d(+abc *d(+*ab) *d(+*abc) *d(+abc*) d(abc*abc*+d*abc*+*abc*+dabc*+d(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。u 逆波兰式计算的设计思想及算法四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。 3、程序输入/输出实例： u 输入以#结束的中缀表达式(包括+ - */（）数字#)。例：(1)（a+b） (2)(a+b*c) (3) B+(-(A)*C输出逆波兰表达式的格式如下：(1) (a+b) ;ab+)(2)(a+b*c)abc*+)(3)B+(-A(A) *CBA)(-)(C*+u 输入中缀表达式并计算结果：a* (b+c)+(-d)#；输出逆波兰式:abc+*d+输入：a=3; b=1;c=2;d=5;计算结果为:4五、实验步骤1、根据流程图编写出各个模块的源程序代码上机调试。2、 编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的逆波兰式的产生及计算程序；直至能够得到完全满意的结果。3、书写实验报告 ；实验报告正文的内容：u 描述逆波兰式的产生及计算程序的设计思想。u 程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。 u 详细的算法描述（程序执行流程图）。u 给出软件的测试方法和测试结果。u 实验总结 （设计的特点、不足、收获与体会）。六、源代码1、操作类package RPNAnalysis;public class RPN_Operation private char expChar = new char100;/表达式栈private int expPointer = 0;/表达式栈指针private char ariStack = new char100;/运算符栈private int top = 0;/运算符栈指针private char exitChar = new char100;/输出栈private int exitPointer = 0;/输出栈指针private String dataStrings = new String10005;/表格数据private String tempString = new String();/临时字符串private String result = new String();/结果字符串private int row = 0;/表格数据行private String compValue = new String();/计算值private final char Arithmetic = +,-,*,/,(,),#;/运算符private final char Letter = a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;/字母表private final char Digit = 1,2,3,4,5,6,7,8,9,0;/数字表public RPN_Operation() for (int i = 0; i 1000; i+) for (int j = 0; j 5; j+) dataStringsij = new String();dataStringsij = ;/判断字符是否为字母public boolean isLetter(char word) int N = 0;while (N Letter.length) if (word = LetterN) return true;N+;return false;/判断字符是否为数字public boolean isDigit(char word) int N = 0;while (N Digit.length) if (word = DigitN) return true;N+;return false;/判断字符是否为算数运算符public boolean isArithmetic(char word) int N = 0;while (N Arithmetic.length) if (word = ArithmeticN) return true;N+;return false;/输出剩余字符串public void printExpChar() tempString = new String();for (int i = expPointer; i expChar.length; i+) tempString += expChari;System.out.print(expChari);result += expChari;System.out.print(tt);result += tt;/输出符号栈public void printAriStack() tempString = new String();for (int i = 0; i top; i+) tempString += ariStacki;System.out.print(ariStacki);result += ariStacki;System.out.print(tt);result += tt;/输出逆波兰式public void printExitChar() tempString = new String();for (int i = 0; i exitPointer; i+) tempString += exitChari;System.out.print(exitChari);result += exitChari;System.out.print(rn);result += rn;/检查字符public boolean checkString(String checkString) char ch;for (int i = 0; i =0 & (ariStacktemp = * | ariStacktemp = /) exitCharexitPointer+ = ariStacktemp;top-;else if (temp=0 & (ariStacktemp = - | ariStacktemp = +)&(expCharexpPointer+1 != * |expCharexpPointer+1 != /) exitCharexitPointer+ = ariStacktemp;top-;while (top= 0 & (ariStacktemp = * | ariStacktemp = /) ) exitCharexitPointer+ = ariStacktemp;top-;ariStacktop+ = ch;System.out.print(row+t+ch+t);result += row+t+ch+t;dataStringsrow0 = row+;dataStringsrow1 = String.valueOf(ch);printExpChar();dataStringsrow2 = tempString;printAriStack();dataStringsrow3 = tempString;printExitChar();dataStringsrow4 = tempString;row+;break;default:break;else if (isLetter(ch) | isDigit(ch) exitCharexitPointer+ = ch;System.out.print(row+t+ch+t);result += row+t+ch+t;dataStringsrow0 = row+;dataStringsrow1 = String.valueOf(ch);printExpChar();dataStringsrow2 = tempString;printAriStack();dataStringsrow3 = tempString;printExitChar();dataStringsrow4 = tempString;row+;ch = expCharexpPointer+;while(top!=0) temp = top - 1; if (ariStacktemp=() top-;continue;exitCharexitPointer+ = ariStack-top;System.out.print(row+t+ch+t);result += row+t+ch+t;dataStringsrow0 = row+;dataStringsrow1 = String.valueOf(ch);printExpChar();dataStringsrow2 = tempString;printAriStack();dataStringsrow3 = tempString;printExitChar();dataStringsrow4 = tempString;row+;/计算值public void compValue() int stack = new int100;exitCharexitPointer+ = #;char ch;int i=0,top=0;ch = exitChari+;while (ch != #) switch (ch) case +:compValue += stacktop-1 + + + stack top;stacktop-1 = stacktop-1 + stack top;compValue += := + stacktop-1 + rn;top-;break;case -:compValue += stacktop-1 + - + stack top;stacktop-1 = stacktop-1 - stack top;compValue += := + stacktop-1 + rn;top-;break;case *:compValue += stacktop-1 + * + stack top;stacktop-1 = stacktop-1 * stack top;compValue += := + stacktop-1 + rn;top-;break;case /:compValue += stacktop-1 + / + stack top;stacktop-1 = stacktop-1 / stack top;compValue += := + stacktop-1 + rn;top-;break;default:top+;stacktop = ch - 0;break;ch = exitChari+;compValue += 结果： + stacktop;System.out.print(compValue);public int getRow() return row;public void setRow(int row) this.row = row;public String getDataStrings() return dataStrings;public void setDataStrings(String dataStrings) this.dataStrings = dataStrings;public String getResult() return result;public void setResult(String result) this.result = result;public char getExitChar() return exitChar;public void setExitChar(char exitChar) this.exitChar = exitChar;public String getCompValue() return compValue;public void setCompValue(String compValue) pValue = compValue;2、界面类package RPNAnalysis;import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.FileWriter;import org.eclipse.swt.widgets.Control;import org.eclipse.swt.widgets.Display;import org.eclipse.swt.widgets.FileDialog;import org.eclipse.swt.widgets.MessageBox;import org.eclipse.swt.widgets.Shell;import org.eclipse.swt.widgets.Menu;import org.eclipse.swt.widgets.TableItem;import org.eclipse.swt.SWT;import org.eclipse.swt.widgets.MenuItem;import org.eclipse.swt.custom.ScrolledComposite;import org.eclipse.swt.custom.TableEditor;import org.eclipse.swt.widgets.Text;import org.eclipse.swt.widgets.Table;import org.eclipse.swt.widgets.TableColumn;import org.eclipse.wb.swt.SWTResourceManager;import org.eclipse.swt.events.ModifyEvent;import org.eclipse.swt.events.ModifyListener;import org.eclipse.swt.events.MouseAdapter;import org.eclipse.swt.events.MouseEvent;import org.eclipse.swt.events.SelectionAdapter;import org.eclipse.swt.events.SelectionEvent;import org.eclipse.swt.graphics.Point;import org.eclipse.swt.graphics.Rectangle;public class RPNSWT protected Shell shell;private Text text;private Table varTable;private Text resultText;private Table resultTable;private MessageBox messageBox;private TableEditor editor;private String result = ;private File sourceFile = null;private RPN_Operation mOperation;private String analysisString;String compValueString = new String();private int varTableRow = 0;private char varTableVar;private char exitChar;/* * Launch the application. * param args */public static void main(String args) try RPNSWT window = new RPNSWT();window.open(); catch (Exception e) e.printStackTrace();/* * Open the window. */public void open() Display display = Display.getDefault();createContents();shell.open();shell.layout();while (!shell.isDisposed() if (!display.readAndDispatch() display.sleep();/* * Create contents of the window. */protected void createContents() shell = new Shell();shell.setSize(500, 386);shell.setText(逆波兰表达式分析器);Menu menu = new Menu(shell, SWT.BAR);shell.setMenuBar(menu);MenuItem menuItem = new MenuItem(menu, SWT.NONE);menuItem.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) newTextTable(););menuItem.setText(u65B0u5EFA);MenuItem menuItem_1 = new MenuItem(menu, SWT.NONE);menuItem_1.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) openFile(););menuItem_1.setText(u6253u5F00);MenuItem menuItem_2 = new MenuItem(menu, SWT.NONE);menuItem_2.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) try analysis(); catch (Exception e2) e2.printStackTrace(););menuItem_2.setText(u5206u6790);MenuItem menuItem_6 = new MenuItem(menu, SWT.NONE);menuItem_6.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) try compValue(); catch (Exception e2) e2.printStackTrace(););menuItem_6.setText(u8BA1u7B97);MenuItem menuItem_3 = new MenuItem(menu, SWT.NONE);menuItem_3.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) saveFile(););menuItem_3.setText(u4FDDu5B58);MenuItem menuItem_4 = new MenuItem(menu, SWT.NONE);menuItem_4.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) shell.dispose(););menuItem_4.setText(u9000u51FA);MenuItem menuItem_5 = new MenuItem(menu, SWT.NONE);menuItem_5.addSelectionListener(new SelectionAdapter() Overridepublic void widgetSelected(SelectionEvent e) messageBox = new MessageBox(shell,SWT.ICON_INFORMATION);messageBox.setText(关于);messageBox.setMessage(逆波兰表达式分析器n 作者：章进兴n 0941901228);messageBox.open(););menuItem_5.setText(u5173u4E8E);ScrolledComposite scrolledComposite = new ScrolledComposite(shell, SWT.BORDER | SWT.H_SCROLL | SWT.V_SCROLL);scrolledComposite.setBounds(10, 10, 202, 119);scrolledComposite.setExpandHorizontal(true);scrolledComposite.setExpandVertical(true);text = new Text(scrolledComposite, SWT.BORDER);scrolledComposite.setContent(text);scrolledComposite.setMinSize(puteSize(SWT.DEFAULT, SWT.DEFAULT);varTable = new Table(shell, SWT.BORDER | SWT.FULL_SELECTION);varTable.setBounds(218, 10, 127, 119);varTable.setHeaderVisible(true);varTable.setLinesVisible(true);editor = new TableEditor(varTable);editor.horizontalAlignment = SWT.LEFT;editor.grabHorizontal = true;createEditorContents();TableColumn tableColumn = new TableColumn(varTable, SWT.NONE);tableColumn.setWidth(61);tableColumn.setText(u53D8u91CF);TableColumn tblclmnNewColumn = new TableColumn(varTable, SWT.NONE);tblclmnNewColumn.setWidth(61);tblclmnNewColumn.setText(u503C);ScrolledComposite scrolledComposite_1 = new ScrolledComposite(shell, SWT.BORDER | SWT.H_SCROLL | SWT.V_SCROLL);scrolledComposite_1.setBounds(351, 10, 123, 119);scrolledComposite_1.setExpandHorizontal(true);scrolledComposite_1.setExpandVertical(true);resultText = new Text(scrolledComposite_1, SWT.BORDER | SWT.H_SCROLL | SWT.V_SCROLL | SWT.CANCEL);resultText.setBackground(SWTResourceManager.getColor(SWT.COLOR_LIST_BACKGROUND);resultText.setEditable(false);scrolledComposite_1.setContent(resultText);scrolledComposite_1.setMinSize(resultTputeSize(SWT.DEFAULT, SWT.DEFAULT);resultTable = new Table(shell, SWT.BORDER | SWT.FULL_SELECTION);resultTable.setBounds(10, 135, 464, 183);resultTable.setHeaderVisible(true);resultTable.setLinesVisible(true);TableColumn tblclmnNewColumn_1 = new TableColumn(resultTable, SWT.NONE);tblclmnNewColumn_1.setResizable(false);tblclmnNewColumn_1.setWidth(59);tblclmnNewColumn_1.setText(u6B65u9AA4);TableColumn tblclmnNewColumn_2 = new TableColumn(resultTable, SWT.NONE);tblclmnNewColumn_2.setWidth(100);tblclmnNewColumn_2.setText(u5F53u524Du7B26u53F7);TableColumn tblclmnNewColumn_3 = new TableColumn(resultTable, SWT.NONE);tblclmnNewColumn_3.setWidth(100);tblclmnNewColumn_3.setText(u8F93u5165u533A);TableColumn tblclmnNewColumn_4 = new TableColumn(resultTable, SWT.NONE);tblclmnNewColumn_4.setWidth(100);tblclmnNewColumn_4.setText(u8FD0u7B97u7B26u53F7u6808);TableColumn tblclmnNewColumn_5 = new TableColumn(resultTable, SWT.NONE);tblclmnNewColumn_5.setWidth(100);tblclmnNewColumn_5.setText(u8F93u51FAu533A);public void openFile() FileDialog openFileDialog = new FileDialog(shell,SWT.OPEN);openFileDialog.setText(选择需要分析的文件);openF