基于Java的中缀表达式转后缀表达式设计

目录
一、实验内容 - 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) {

        }
    }
}