目录
一、实验内容 - 1 -
二、实验要求 - 1 -
三、 运行环境 - 1 -
四、 实验原理 - 1 -
1.中缀表达式转后缀表达式 - 2 -
2. 后缀表达式的计算 - 2 -
五、 具体实验设计 - 2 -
六、 运行结果：如图所示 - 5 -
七、 实验心得与体会 - 7 -
一、实验内容
中缀表达式转后缀表达式
二、实验要求
1、实现一个完整的 Java 程序，它读取文件中的中缀表达式（每个表达式以分号结束，文件中可以有多个表达式）并转换为等价的后缀表达式后输出到屏幕上。
2、表达式中的运算量可以是任意整数或者小数，支持加、减、乘、除、取负运算以及小括号，表达式中的空格、制表符等空白符号可以被忽略。
3、若用户输入的表达式有误，则提示用户错误的位置。譬如两个运算量之间缺少运算符、或运算符缺少左（或右）运算量等。错误处理功能的最低要求是当输入表达式有错时，给出一个报错信息，提示错误的位置和类别。
学有余力的学生还可考虑尝试如何实现出错恢复（Error Recovery），即当程序发现一个错误时不是立马停下来，而是能够从跌倒的地方爬起来，继续分析下去，从而一次运行即可发现更多的错误。
4、为以上的 Java 程序提供一个随机测试数据发生器（用 Java 语言来写），生成若干随机的正确表达式和不正确表达式（通过命令行参数决定是生成正确的还是不正确的以及生成的数量）。生成的测试数据要求写入文件，可以被 1 中的程序读取。
三、运行环境
1、操作系统：Windows10
2、软件：eclipse
3、硬件：i5-520m CPU+8G内存
本文转载自：http://www.biyezuopin.vip/onews.asp?id=15781
四、实验原理
在计算一个表达式的时候，可以用数据结构中栈的知识，将我们平常熟悉的中缀表达式转为后缀表达式，再将后缀表达式进行计算得到结果。先说下什么是中缀什么是后缀：
中缀表达式：eg: 9+(3-1)*3+10/2，就是我们平常计算时的表达式；
后缀表达式：eg: 9 3 1 - 3 * + 10 2 / + ，不包含括号，运算符在两个运算对象后面的表达式。
package analyse;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.List;
/*
* 一些基本语法:
exp -> exp {addop term}
addop -> + \ -
term -> Negative {mulop Negative}
mulop -> *|/
Nagative -> -factor|factor
factor -> (exp) |number
*/
class StateAnalyze {
public LinkedList<Toke> tokes;
public Toke tok;
public int index;
String fail;
public String output="";
public StateAnalyze(LinkedList<Toke> list)
{
this.tokes=list;
}
public void Error(String a) throws CodeException
{
System.err.print(a);
throw new CodeException(a);
}
public void match(String a) throws CodeException
{
if (tok.word.equals(a)||tok.type.equals(a))
{
if (index<tokes.size())
{
tok=tokes.get(index++);
}
}
else
{
Error("wrong word! expected："+a+" actually:"+tok.word+"index:"+(index+1)+";line:"+tok.line);
}
}
public void start_analyse()
{
index=0;
try {
tok= tokes.get(index++);
exp();
}catch (CodeException e)
{
fail=e.message;
}
}
public void exp() throws CodeException
{
term();
while(tok.word.equals("+")||tok.word.equals("-"))
{
String s=tok.word;
match(tok.word);
term();
output+=s;
output+="|";
}
}
public void term() throws CodeException
{
Negative();
while (tok.word.equals("*")||tok.word.equals("/"))
{
String s=tok.word;
match(tok.word);
Negative();
output+=s;
output+="|";
}
}
public void Negative() throws CodeException
{
if (tok.word.equals("-"))
{
String s=tok.word;
match("-");
output+=s;
factor();
}
else factor();
}
public void factor() throws CodeException
{
char c=tok.word.charAt(0);
if (tok.word.equals("("))
{
match("(");
exp();
match(")");
}
else if (tok.type.equals("number"))
{
int temp=Integer.parseInt(tok.word);
String s=tok.word;
match("number");
output+=s;
output+="|";
}
else Error("不是合法的表达式！！！ (列:"+(index)+",行:"+tok.line+")");
}
public static void main(String args[])
{
Users users=new Users("test.txt");
System.out.println(users.wordAnalyse.tokes);
users.stateAnalyze.start_analyse();
System.out.println(users.stateAnalyze.output);
}
}
class CodeException extends Exception {
public String message;
public CodeException(String s)
{
super();
message=s;
}
}
/*
* 一些基本语法:
exp -> exp {addop term}
addop -> + \ -
term -> Negative {mulop Negative}
mulop -> *|/
Nagative -> -factor|factor
factor -> (exp) |number
*/
class Users {
public WordAnalyse wordAnalyse;
public StateAnalyze stateAnalyze;
public String name;
public Users(String filepath)
{
try {
BufferedReader bufferedReader=new BufferedReader(new FileReader(filepath));
StringBuffer stringBuffer=new StringBuffer();
String line=bufferedReader.readLine();
while(line!=null)
{
stringBuffer.append(line+'\n');
line=bufferedReader.readLine();
}
name=filepath;
wordAnalyse=new WordAnalyse(stringBuffer.toString());
wordAnalyse.analyse();
stateAnalyze=new StateAnalyze(wordAnalyse.tokes);
}
catch (Exception e)
{
e.printStackTrace();
}
}
public Users(){}
}
class Toke {
//public static int no=0;
int number;
String word;
String type;
int line;
public Toke(int n, int l)
{
this.number=n;
this.line=l;
}
@Override
public String toString() {
return number+"+"+word+"+"+type+'\n';
}
}
//词法分析器
public class WordAnalyse {
public LinkedList<Toke> tokes;
public String source;
int no;
int line;
final static int NUMBER=1;
final static int CHAR=2;
final static int START=0;
public static HashSet<String> reserer=new HashSet<>();
public WordAnalyse(String s){
source=s;
tokes =new LinkedList<>();
no=0;
line=1;
}
public int getWhat(char c)
{
if(c<='9'&&c>='0')
return NUMBER;
else return CHAR;
}
public List<Toke> analyse()
{
int index=0;
int state=0;
String temp="";
while(index<source.length())
{
char cur=source.charAt(index);
if (state==START)
{
state=getWhat(cur);
}
switch (state)
{
case NUMBER:
if ((cur>='0'&&cur<='9')||cur=='.')
{
temp=temp+cur;
cur=source.charAt(index++);
continue;
}
else{
Toke t=new Toke(no++,line);
t.word=temp;
t.type="number";
tokes.addLast(t);
temp="";
state=START;
}
break;
case CHAR:
switch (cur)
{
case '\n':
line++;
index++;
state=START;
break;
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
Toke t=new Toke(no++,line);
temp=temp+cur;
t.type="character";
t.word=temp;
tokes.addLast(t);
state=START;
temp="";
index++;
break;
default:
index++;
state=START;
break;
}
break;
}
}
return tokes;
}
//测试
public static void main(String args[]) {
StringBuffer all = new StringBuffer();
try {
BufferedReader reader = new BufferedReader(new FileReader("test.txt"));
String line = reader.readLine();
while (line != null) {
all.append(line);
all.append('\n');
line = reader.readLine();
}
WordAnalyse w = new WordAnalyse("1--2-3"+"\n");
w.analyse();
System.out.print(w.source);
System.out.println();
System.out.println();
System.out.println();
System.out.println(w.tokes);
} catch (Exception e) {
}
}
}
