表达式求值

实验5  表达式求值

实验目的

1．  会定义顺序栈和链栈的结点类型。

2．  掌握栈的插入和删除结点在操作上的特点。

3．  熟悉对栈的一些基本操作和具体的函数定义。

实验内容

程序1

该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。

/* 定义DataType为int类型 */

typedef int DataType;

 

/* 栈的结点类型 */

#define MAXSIZE  1024  

typedef  struct

{DataType  data[MAXSIZE];

int  top;

}SeqStack;

 

/* 初始化顺序栈 */

SeqStack  SeqStackInit()

 

/* 检查顺序栈是否为空 */

int SeqStackEmpty(SeqStack S)

 

/* 把S置为空栈 */

void ClearStack(SeqStack  S)

 

/* 把元素x压入栈，使其成为新的栈顶元素 */

void SeqStackPush(SeqStack S,DataType x)

 

/* 把栈顶元素弹出 */

DataType SeqStackPop(SeqStack S)

 

/* 取栈顶元素 */

DataType SeqStackGetTop(SeqStack S)

 

/*输出顺序栈中的元素*/

void SeqStackPrint(SeqStack S)

 

程序2 用顺序栈实现算术表达式求值。

将表达式看成字符串序列，输入语法正确、不含有变量的整数表达式（表达式中的数字限为单位数），利用算符的优先关系，把中序表达式转换为后序表达式后输出，然后求出该后序表达式的值。

例如：输入的表达式为2*(6-4)+8/4

转换后得到的后序表达式为264-*84/+

设计要求：在程序中构造六个子程序分别为

int empty(SeqStack stack); /*检查栈是否为空*/

int operation(char op); /*判断是否为运算符*/

int priority(char op); /*判断运算符的优先权*/

SeqStack push(SeqStack stack,char value); /*入栈*/

SeqStack pop(SeqStack stack,char *value); /*出栈*/

double count(char *backorder); /*计算逆波兰表达式的值*/

 

程序3 用链栈实现算术表达式求值。（与程序2的基本要求相同）

链栈结点的类型描述如下：

typedef int DataType;

typedef  struct StackNode

{DataType data;

struct StackNode *next;

}StackNode，*LinkedStack;

“运算符优先级表” - 参考博客：http://www.jb51.net/article/37289.htm

/* 程序1
该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。
*/
#include <stdio.h>
#include <stdlib.h>
/* 定义DataType为int类型 */
typedef int DataType;
 
/* 栈的结点类型 */
#define MAXSIZE  1024  
typedef  struct{
    DataType  data[MAXSIZE];
    int  top;
}SeqStack;
 
/* 初始化顺序栈 */
SeqStack  SeqStackInit()
{
    SeqStack q;
    q.top = -1;
    return q;
}
 
/* 检查顺序栈是否为空 */
int SeqStackEmpty(SeqStack S)
{
    if(S.top==-1)    //栈空
        return 1;
    else 
        return 0;
}
 
/* 把S置为空栈 */
void ClearStack(SeqStack  &S)
{
    S.top = -1;
}
 
/* 把元素x压入栈，使其成为新的栈顶元素 */
void SeqStackPush(SeqStack &S,DataType x)
{
    if(S.top==MAXSIZE-1)    //已经满了
        printf("入栈失败，栈已满！
");
    else {
        S.top++;
        S.data[S.top] = x;
    }
}
 
/* 把栈顶元素弹出 */
DataType SeqStackPop(SeqStack &S)
{
    if(S.top==-1){    //栈已空
        printf("出栈失败，栈已空！
");
        return 0;
    }
    else {
        DataType x = S.data[S.top--];
        return x;
    }
}
 
/* 取栈顶元素 */
DataType SeqStackGetTop(SeqStack S)
{
    return S.data[S.top];
}
 
/*输出顺序栈中的元素*/
void SeqStackPrint(SeqStack S)
{
    int top = S.top;
    while(top!=-1)
        printf("%d
",S.data[top--]);
}

int Menu()    //显示菜单，返回命令
{
    int in;
    printf("[1] 检查顺序栈是否为空
");
    printf("[2] 把S置为空栈
");
    printf("[3] 把元素x压入栈，使其成为新的栈顶元素
");
    printf("[4] 把栈顶元素弹出
");
    printf("[5] 取栈顶元素
");
    printf("[6] 输出顺序栈中的元素
");
    printf("[0] 按其它键退出
");
    scanf("%d",&in);
    return in;
}
void Reply(int in,SeqStack &S)    //对命令的反应
{
    int x;
    switch(in){
    case 1:
        if(SeqStackEmpty(S))
            printf("栈为空！
");
        else 
            printf("栈未空！
");
        break;
    case 2:
        ClearStack(S);    //将S置为空栈
        printf("已成功置为空栈！
");
        break;
    case 3:
        printf("请输入你要压栈的元素：
");
        scanf("%d",&x);
        SeqStackPush(S,x);
        break;
    case 4:
        SeqStackPop(S);
        break;
    case 5:
        if(SeqStackEmpty(S))
            printf("栈当前为空，栈顶无元素！
");
        else
            printf("栈顶元素为：%d
",SeqStackGetTop(S));
        break;
    case 6:
        if(SeqStackEmpty(S))
            printf("栈当前为空！
");
        else{ 
            printf("栈中元素为（从顶至下）：
");
            SeqStackPrint(S);
        }
        break;
    default:
        exit(1);
    }
    system("pause");
    system("cls");
}
int main()
{
    SeqStack S = SeqStackInit();
    while(1){
        int in = Menu();
        Reply(in,S);
    }
    return 0;
}

  1 /* 程序2 用顺序栈实现算术表达式求值。
  2 将表达式看成字符串序列，输入语法正确、不含有变量的整数表达式（表达式中的数字限为单位数）
  3 利用算符的优先关系，把中序表达式转换为后序表达式后输出，然后求出该后序表达式的值。
  4 例如：输入的表达式为2*(6-4)+8/4
  5 转换后得到的后序表达式为264-*84/+
  6 设计要求：在程序中构造六个子程序分别为
  7 */
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 /* 定义DataType为int类型 */
 11 typedef char DataType;
 12  
 13 /* 栈的结点类型 */
 14 #define MAXSIZE  1024  
 15 typedef  struct{
 16     char data[MAXSIZE];
 17     int  top;
 18 }SeqStack;
 19 SeqStack op;    //运算符栈和表达式栈
 20 
 21 int Prior[6][6] =    //Prior[lop][rop]
 22 { // 运算符优先级表 
 23  // '+' '-' '*' '/' '(' ')'
 24  /*'+'*/-1,-1,1,1,1,-1,
 25  /*'-'*/-1,-1,1,1,1,-1,
 26  /*'*'*/-1,-1,-1,-1,1,-1,
 27  /*'/'*/-1,-1,-1,-1,1,-1,
 28  /*'('*/1,1,1,1,1,0,
 29  /*')'*/-1,-1,-1,-1,0,-1
 30 };
 31 
 32 int empty(SeqStack stack) /*检查栈是否为空*/
 33 {
 34     if(stack.top==-1)    //栈空
 35         return 1;
 36     else 
 37         return 0;
 38 }
 39 int operation(char op) /*判断是否为运算符*/
 40 {
 41     if('0'<=op && op<='9')    //是单位数字，不是运算符
 42         return 0;
 43     else 
 44         return 1;
 45 }
 46 int priority(char rop) /*判断运算符的优先权*/
 47 {
 48     char lop = op.data[op.top];
 49     int a,b;
 50     switch(lop){
 51     case '+':a=0;break;
 52     case '-':a=1;break;
 53     case '*':a=2;break;
 54     case '/':a=3;break;
 55     case '(':a=4;break;
 56     case ')':a=5;break;
 57     default:break;
 58     }
 59     switch(rop){
 60     case '+':b=0;break;
 61     case '-':b=1;break;
 62     case '*':b=2;break;
 63     case '/':b=3;break;
 64     case '(':b=4;break;
 65     case ')':b=5;break;
 66     default:break;
 67     }
 68     return Prior[a][b];
 69 }
 70 SeqStack push(SeqStack stack,char value) /*入栈*/
 71 {
 72     if(stack.top==MAXSIZE-1)    //已经满了
 73         printf("入栈失败，栈已满！
");
 74     else {
 75         stack.top++;
 76         stack.data[stack.top] = value;
 77     }
 78     return stack;
 79 }
 80 SeqStack pop(SeqStack stack,char *value) /*出栈*/
 81 {
 82     if(stack.top==-1){    //栈已空
 83         printf("出栈失败，栈已空！
");
 84         return stack;
 85     }
 86     else {
 87         *value = stack.data[stack.top--];
 88         return stack;
 89     }
 90 }
 91 double count(char *backorder) /*计算逆波兰表达式的值*/
 92 {
 93     struct {
 94         double data[MAXSIZE];
 95         int top;
 96     } ds;    //数栈
 97     ds.top = -1;
 98     int i;
 99     for(i=0;backorder[i];i++)
100         if(operation(backorder[i])){    //是运算符
101             double a,b;
102             b = ds.data[ds.top--];    //从数栈中依次取出两个数
103             a = ds.data[ds.top--];
104             switch(backorder[i]){    //运算并入栈
105             case '+':ds.top++;ds.data[ds.top] = a+b;break;
106             case '-':ds.top++;ds.data[ds.top] = a-b;break;
107             case '*':ds.top++;ds.data[ds.top] = a*b;break;
108             case '/':ds.top++;ds.data[ds.top] = a/b;break;
109             default:break;
110             }
111         }
112         else{    //是数，直接入数栈
113             ds.top++;
114             ds.data[ds.top] = double(backorder[i] - '0');
115         }
116     return ds.data[ds.top];
117 }
118 void trans(char exp[],char backorder[])    //将中序表达式转换成后缀表达式，存储一字符串中
119 {
120     int index=0;
121     int len = 0;
122     while(exp[index]){
123         if(operation(exp[index])){    //是运算符
124             if(empty(op)){    //如果运算符栈为空，直接入栈
125                 op = push(op,exp[index++]);
126             }
127             else{    //运算符栈不为空，与将该运算符与栈顶运算符比较
128                 char c;
129                 switch(priority(exp[index])){
130                 case 1:    //当前运算符比栈顶运算符优先级高
131                     op = push(op,exp[index++]);
132                     break;
133                 case 0:    //运算符优先级相等。只出现在栈顶为'('和当前为')'的情况
134                     op = pop(op,&c);
135                     index++;
136                     break;
137                 case -1:    //当前运算符优先级低
138                     op = pop(op,&c);    //退栈 
139                     backorder[len++] = c;    //将运算符放入字符串中
140                     break;
141                 default:break;
142                 }
143             }
144         }
145         else{    //是数字。直接压栈
146             backorder[len++] = exp[index++];    //将数字放入字符串中
147         }
148     }
149     while(!empty(op)){    //如果运算符栈不为空，全部出栈
150         char c;
151         op = pop(op,&c);    //退栈 
152         backorder[len++] = c;    //将运算符放入字符串中
153     }
154     backorder[len] = '';
155 }
156 void print(char backorder[])    //输出表达式栈中的式子
157 {
158     int i;
159     for(i=0;backorder[i];i++)
160         printf("%c",backorder[i]);
161     printf("
");
162 }
163 int main()
164 {
165     char exp[MAXSIZE];
166     char backorder[MAXSIZE];
167     printf("[1] 请输入中缀表达式：
");
168     while(scanf("%s",exp)!=EOF){
169         //初始化
170         op.top = -1;
171         //输出转换后的后缀表达式
172         trans(exp,backorder);
173         printf("[2] 其后缀表达式为：
");
174         print(backorder);
175         //计算后缀表达式的结果
176         printf("[3] 后缀表达式的结果：
");
177         printf("%lf
",count(backorder));
178         //为下一次输入做准备
179         printf("
");
180         printf("请输入中缀表达式：
");
181     }
182     return 0;
183 }

  1 /* 程序3 用链栈实现算术表达式求值。（与程序2的基本要求相同）
  2 */
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 
  6 /* 栈的结点类型 */
  7 #define MAXSIZE  1024
  8 
  9 //链栈结点的类型描述如下：
 10 typedef char DataType;
 11 typedef  struct StackNode{
 12     DataType data;
 13     struct StackNode *next;
 14 } StackNode,*LinkedStack;
 15 
 16 LinkedStack op;    //运算符栈和表达式栈
 17 
 18 int Prior[6][6] =    //Prior[lop][rop]
 19 { // 运算符优先级表 
 20  // '+' '-' '*' '/' '(' ')'
 21  /*'+'*/-1,-1,1,1,1,-1,
 22  /*'-'*/-1,-1,1,1,1,-1,
 23  /*'*'*/-1,-1,-1,-1,1,-1,
 24  /*'/'*/-1,-1,-1,-1,1,-1,
 25  /*'('*/1,1,1,1,1,0,
 26  /*')'*/-1,-1,-1,-1,0,-1
 27 };
 28 
 29 int empty(LinkedStack &stack) /*检查栈是否为空*/
 30 {
 31     if(stack->next==NULL)    //栈空
 32         return 1;
 33     else
 34         return 0;
 35 }
 36 int operation(char op) /*判断是否为运算符*/
 37 {
 38     if('0'<=op && op<='9')    //是单位数字，不是运算符
 39         return 0;
 40     else 
 41         return 1;
 42 }
 43 int priority(char rop) /*判断运算符的优先权*/
 44 {
 45     char lop = op->next->data;
 46     int a,b;
 47     switch(lop){
 48     case '+':a=0;break;
 49     case '-':a=1;break;
 50     case '*':a=2;break;
 51     case '/':a=3;break;
 52     case '(':a=4;break;
 53     case ')':a=5;break;
 54     default:break;
 55     }
 56     switch(rop){
 57     case '+':b=0;break;
 58     case '-':b=1;break;
 59     case '*':b=2;break;
 60     case '/':b=3;break;
 61     case '(':b=4;break;
 62     case ')':b=5;break;
 63     default:break;
 64     }
 65     return Prior[a][b];
 66 }
 67 LinkedStack push(LinkedStack &stack,char value) /*入栈*/
 68 {
 69     LinkedStack p = (LinkedStack)malloc(sizeof(StackNode));
 70     p->data = value;
 71     p->next = stack->next;
 72     stack->next = p;
 73     return stack;
 74 }
 75 LinkedStack pop(LinkedStack &stack,char *value) /*出栈*/
 76 {
 77     if(stack->next==NULL){    //栈已空
 78         printf("出栈失败，栈已空！
");
 79         return stack;
 80     }
 81     else {
 82         LinkedStack p = stack->next;
 83         stack->next = p->next;
 84         *value = p->data;
 85         free(p);
 86         return stack;
 87     }
 88 }
 89 double count(char *backorder) /*计算逆波兰表达式的值*/
 90 {
 91     typedef struct DigitStack{
 92         double data;
 93         DigitStack *next;
 94     } DigitStack,*LinkedDS;    //数栈
 95     LinkedDS ds = (LinkedDS)malloc(sizeof(DigitStack));
 96     LinkedDS p;
 97     ds->next = NULL;    //初始化
 98     int i;
 99     for(i=0;backorder[i];i++)
100         if(operation(backorder[i])){    //是运算符
101             double a,b;
102             p = ds->next;    //从数栈中依次取出两个数
103             ds->next = p->next;
104             b = p->data;
105             free(p);
106             p = ds->next;
107             ds->next = p->next;
108             a = p->data;
109             free(p);
110             p = (LinkedDS)malloc(sizeof(DigitStack));
111             switch(backorder[i]){    //运算并入栈
112             case '+':
113                 p->data = a+b;
114                 p->next = ds->next;
115                 ds->next = p;
116                 break;
117             case '-':
118                 p->data = a-b;
119                 p->next = ds->next;
120                 ds->next = p;
121                 break;
122             case '*':
123                 p->data = a*b;
124                 p->next = ds->next;
125                 ds->next = p;
126                 break;
127             case '/':
128                 p->data = a/b;
129                 p->next = ds->next;
130                 ds->next = p;
131                 break;
132             default:break;
133             }
134         }
135         else{    //是数，直接入数栈
136             p = (LinkedDS)malloc(sizeof(DigitStack));
137             p->data = double(backorder[i] - '0');
138             p->next = ds->next;
139             ds->next = p;
140         }
141     return ds->next->data;
142 }
143 void trans(char exp[],char backorder[])    //将中序表达式转换成后缀表达式，存储一字符串中
144 {
145     int index=0;
146     int len = 0;
147     while(exp[index]){
148         if(operation(exp[index])){    //是运算符
149             if(empty(op)){    //如果运算符栈为空，直接入栈
150                 op = push(op,exp[index++]);
151             }
152             else{    //运算符栈不为空，与将该运算符与栈顶运算符比较
153                 char c;
154                 switch(priority(exp[index])){
155                 case 1:    //当前运算符比栈顶运算符优先级高
156                     op = push(op,exp[index++]);
157                     break;
158                 case 0:    //运算符优先级相等。只出现在栈顶为'('和当前为')'的情况
159                     op = pop(op,&c);
160                     index++;
161                     break;
162                 case -1:    //当前运算符优先级低
163                     op = pop(op,&c);    //退栈 
164                     backorder[len++] = c;    //将运算符放入字符串中
165                     break;
166                 default:break;
167                 }
168             }
169         }
170         else{    //是数字。直接压栈
171             backorder[len++] = exp[index++];    //将数字放入字符串中
172         }
173     }
174     while(!empty(op)){    //如果运算符栈不为空，全部出栈
175         char c;
176         op = pop(op,&c);    //退栈 
177         backorder[len++] = c;    //将运算符放入字符串中
178     }
179     backorder[len] = '';
180 }
181 void print(char backorder[])    //输出表达式栈中的式子
182 {
183     int i;
184     for(i=0;backorder[i];i++)
185         printf("%c",backorder[i]);
186     printf("
");
187 }
188 void Destroy(LinkedStack &op)
189 {
190     while(op->next){
191         LinkedStack p = op->next;
192         op->next = p->next;
193         free(p);
194     }
195 }
196 int main()
197 {
198     char exp[MAXSIZE];
199     char backorder[MAXSIZE];
200     op = (LinkedStack)malloc(sizeof(StackNode));
201     printf("[1] 请输入中缀表达式：
");
202     while(scanf("%s",exp)!=EOF){
203         //初始化
204         op->next = NULL;
205         //输出转换后的后缀表达式
206         trans(exp,backorder);
207         printf("[2] 其后缀表达式为：
");
208         print(backorder);
209         //计算后缀表达式的结果
210         printf("[3] 后缀表达式的结果：
");
211         printf("%lf
",count(backorder));
212         //为下一次输入做准备
213         Destroy(op);
214         printf("
");
215         printf("请输入中缀表达式：
");
216     }
217     return 0;
218 }