编译原理实验三(逆波兰式的产生及计算)


说明

实验代码采用多文件的形式,即包含三部分:

  1. Rp.h : 结构体以及类(成员函数等)的声明
  2. Rp.cpp : 类的成员函数的实现
  3. main.cpp : 主调函数, 完成用户输入的过滤以及类的的实例化

实验流程图

Alt

实验代码

  • Rp.h
// Rp.h
#ifndef RP_H
#define RP_H

#define LEN 20 // 定义输入字符长度

struct fake_stack
{
    char value; // 存储字符
    fake_stack *fd; // 前驱指针
    fake_stack *bk; // 后驱指针
};

struct values
{
    int v;  // 记录运算量的值
    char v_c;   // 记录运算量符号
    values *next;
};

class Rp
{
    public:
        Rp(char input[]); // 构造函数,接收输入的表达式
        void Rpn();  // 生成逆波兰式
        void Calculate();   // 计算逆波兰式
        int compare(char arg1,char arg2);  // 判断优先级
        // arg1>arg2;return 1   arg1<=arg2;return 0
        int compare1(char ch);  // compare 子函数
        void show(char ch, char *in, char *out);    // 输出分析过程
        int getNum(char ch, int value);    // 获取对应运算量的值
        bool isNum(char p); // 判断是否属于运算量
        void stack_pop(char *ch); // 模拟弹栈操作
        void stack_push(char ch); // 模拟压栈操作
    private:
        fake_stack *bp,*sp; // 栈指针
        char input[LEN],output[LEN];
        values *head;   // 记录运算量的单链表头指针
};

#endif
  • Rp.cpp
// Rp.cpp
#include "Rp.h"
#include <iostream>
#include <cstring>
using namespace std;

void Rp::stack_pop(char *ch)
{
    // 模拟弹栈操作
    fake_stack *p;
    p = sp;
    *ch = p->value;
    sp = sp->fd;
    sp->bk = NULL;
    p->fd = NULL;
    delete p;
}

void Rp::stack_push(char ch)
{
    // 模拟压栈操作
   fake_stack *q;
   q = new fake_stack;
   q->value = ch;
   q->bk = NULL;
   q->fd = sp;
   sp->bk = q;
   sp = q;
}

bool Rp::isNum(char ch)
{
    // 约定输入的表达式为小写字母和运算符组成
    if(ch < 'z' && ch >= 'a')
        return true;
    return false;
}

int Rp::getNum(char ch, int value)
{
    if(ch == 'T')
        return value;
    values *p;
    p = head;
    while(p!=NULL){
        if(p->v_c == ch)
            return p->v;
        p = p->next;
    }
    cout<<"get num failed!"<<endl;
    return 0;
}
void Rp::show(char ch, char *in, char *out)
{
    fake_stack *p;
    string stack;
    p = bp;
    do{
        stack += p->value;
        p = p->bk;
    }while(p != NULL);
    cout<<ch;
    cout.width(20);
    cout<<in;
    cout.width(20);
    cout<<stack;
    cout.width(20);
    cout<<output;
    cout<<endl;
}

int Rp::compare1(char ch)
{
    switch (ch)
    {
    case '+': return 1;
    case '-': return 1;
    case '*': return 2;
    case '/': return 2;
    default:
        return -1; // 不合法运算符的情况
    }
}
int Rp::compare(char arg1, char arg2)
{
    int t1,t2;  // 记录运算符优先级
    if(t1 = compare1(arg1))
    if(t2 = compare1(arg2))
    if(t1<=t2)
        return 0;
    return 1;
}

void Rp::Calculate()
{
    char *p = output;
    char value1,value2; // 临时存储要计算的变量
    char res = 'T'; // 作为存储临时计算结果的标志
    int c_res;  // 存储临时计算结果
    while(*p != '#'){
        if(isNum(*p)){
            stack_push(*p);
            p++;
        }else{
            stack_pop(&value2);
            stack_pop(&value1);
            switch (*p)
            {
            case '+':{
                stack_push(res);
                c_res = getNum(value1, c_res) + getNum(value2, c_res);
                p++;
                break;
            }
            case '-':{
                stack_push(res);
                c_res = getNum(value1, c_res) - getNum(value2, c_res);
                p++;
                break;
            }
            case '*':{
                stack_push(res);
                c_res = getNum(value1, c_res) * getNum(value2, c_res);
                p++;
                break;
            }
            case '/':{
                stack_push(res);
                c_res = getNum(value1, c_res) / getNum(value2, c_res);
                p++;
                break;
            }
            default:{
                cout<<"Erro!";
                break;
            }
            }
        }
    }
    cout<<"\nCalculate result: "<<c_res<<endl;
}

void Rp::Rpn()
{
    char *in(input),*out(output); // 输入、输出缓冲区指针
    cout<<"current\t\t"<<"input\t\t"<<"sym stack\t\t"<<"output"<<endl;
    char ch;
    ch = *in; // 获取当前字符
    in++; // 指向下一个输入字符
    while (ch != '#'){
        if(isNum(ch)){// 是运算量的情况
            *out = ch;
            out++;
            ch = *in;
            in++;
            show(ch,in,output);
        }else if(ch != '(' && ch!= ')'){// 运算符
            if(sp->value == '#'){// 符号栈为空
                stack_push(ch);
                ch = *in;
                in++;
                show(ch,in,output);
            }else{// 符号栈不为空
                L:
                int t = compare(ch,sp->value);
                switch (t)
                {
                case 1:{
                    stack_push(ch);
                    ch = *in;
                    in++;
                    show(ch,in,output);
                    break;
                    }
                default:{
                    stack_pop(out);
                    show(ch,in,output);
                    out++;
                    goto L;
                    }
                }
            }
        }else if(ch == '('){
            stack_push(ch);
            show(ch,in,output);
            ch = *in;
            in++;
        }else if(ch == ')'){
            L1:
            if(sp->value == '('){
                char trash;
                stack_pop(&trash);
                show(ch,in,output);
                ch = *in;
                in++;
            }else if(sp->value == '#')
                cout<<"Erro!"<<endl;
            else{
                stack_pop(out++);
                show(ch,in,output);
                goto L1;
            }
        }else{
            while(sp->value == '#'){
                if(sp->value != '('){
                    stack_pop(out++);
                    show(ch,in,output);
                }else
                    cout<<"Erro!"<<endl;
            }
        }
    }
    if(sp->value != '#'){
        stack_pop(out++);
        show(ch,in,output);
    }
    *out = '#'; // 为output添加结束标志
    while(sp!=bp){
        char temp;
        stack_pop(&temp);
    }// 清空栈
}

Rp::Rp(char inputs[])
{
    strcpy(input,inputs);   // 拷贝输入到模拟缓冲区
    // 初始化栈空间
    bp = new fake_stack;
    bp->value = '#';
    sp = bp;
    bp->fd = NULL;
    bp->bk = NULL;
    head = new values;
    values *p;
    p = head;
    char temp;
    cout<<"\nPlease input sym and value(press E to end input): "<<endl;
start:
    cout<<"\nsym: ";
    cin>> temp;
    if(temp == 'E')
        goto run;
    p->v_c = temp;
    cout<<"value: ";
    cin>> p->v;
    p->next = new values;
    p = p->next;
    goto start;
run:
    fflush(stdin);
    fflush(stdout);
    Rpn();  // 产生逆波兰式
    Calculate(); // 计算表达式结果
}
  • main.cpp
// main.cpp
#include "Rp.h"
#include <iostream>
using namespace std;

int main()
{
    char in[LEN];
s:
    cout<<"Enter a string ending in #: ";
    cin>>in;
    char *q=in;
    while (*q!='#')
    {
        if( !((*q >='a' && *q <='z')||\
             (*q == '+' ||\
              *q == '-' ||\
              *q == '*' ||\
              *q == '/' ||\
              *q == '(' ||\
              *q == ')'))){
            cout<<"wrong input!"<<endl;
            goto s;
        }
        q++;
    }
    Rp p(in);
}