表达式求值

题目描述

算数四则运算的规则是1）先乘除，后加减；2）从左算到右；3）先括号内，后括号外。

由此，算式$4+2*3-10/5$的计算顺序为$4+2*3-10/5=4+6-10/5=4+6-2=8$。

给定一个以“#”作为结束符的算式，求出算式的结果。

给出严蔚敏《数据结构（C语言）》中的一段算法描述以作参考：

图1：表达式求值算法

图2：表达式求值算法（续）

图3：表达式求值算法（续）

输入

以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

输出

输出表达式运算的结果。

样例输入

4+2*3-10/5#
3*(7-2)#
2*3/2#

样例输出

8
15
3

提示

使用栈来解决本题，很多人都会想到。但怎样建栈，却带来了问题。同样，严书上的代码实际上也给大家带来了问题。看过严书光盘中代码的人应该知道，代码中使用了两个栈，一个是存储运算符的，类型为char；另一个存储运算数，类型为float。而操作两个栈的函数都一样。要知道，除非像C++中使用泛型，C语言中却基本不能实现这样的操作。所以在C语言环境中需要将这两个栈结合在一起。由于char与int有种特别的联系，可以使用int来代替char存储运算符。

注意灵活运用栈，要是能够学习C++使用template就更好了。可以模拟STL了。

题解

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define stack_size 100
#define stackzengsize 10
 
char str[1000];
 
typedef struct {

int *base;
int *top;
int stacksize;
}sqstack;
 
 
char yunsuanfu[7] = {'+','-','*','/','(',')','#'};
 
unsigned char prior[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'<','<','<','<','<',' ','>'},
{'<','<','<','<','<',' ','='}};
 
int chushihua(sqstack *s)
{
s->base = (int *)malloc(sizeof(int) * stack_size);
if( !s->base) //分配失败
{
exit(0);
 } 
s->top = s->base;
s->stacksize = stack_size;
return 1;
}
 
int push(sqstack *s,int x)  //入栈 
{
//如果栈已满，在申请·额外·空间
if((s->top - s->base) >= s->stacksize)
{
s->base = (int *)realloc(s->base,(s->stacksize + stackzengsize)*sizeof(int));
if(!s->base)
{
exit(0);
}
s->stacksize = s->stacksize + stackzengsize;
}
*(s->top)++ = x;

return 1;
}
 
int gettop(sqstack *s) //获取栈顶元素 
{
if(s->base == s->top)
{
return 0;
}
int x = *(s->top - 1);
return x;
}
 
int yunsuan_fu(char ch,char str[])
{
int i;
for(i = 0; ch != str[i] ; i++)
{
}
if(i < 7)
{
return 1;
}

return 0;
}
 
void lianjie(char *s1,char *s2) //把字符串 2 连接到 1 的后面 
{
int i = 0;
int j = 0;
while(s1[i] != '\0')
{
i++;
}
while(s2[j] != '\0')
{
s1[i++] = s2[j++];
}

s1[i] = '\0';
}
 
int AToi(char *str)
{
int i = 0;
int x = 0;
while(str[i] != '\0')
{
x = x * 10 + str[i] -'0';
i++;
}

return x;
 } 
 
 int youxianji(char x,char y)
 {
 int i = 0;
 int j = 0;
 while(x != yunsuanfu[i])
 {
 i++;
}
while(y != yunsuanfu[j])
{
j++;
}
return prior[i][j];
 }
 
 int pop(sqstack *s)  //脱括号
 {
 if(s->base == s->top)
 {
 return 0;
 }
 
 int x = *--(s->top);
 return x;
  } 
  
int yunsuan(int x,int y,int z)  //运输
{
  switch(y)
  {
  case '+':
  return x + z;
  case '-':
  return x - z;
  case '*':
  return x * z;
  case '/':
  return x / z;
  
}
} 
 
int Biaodashi(char *biaodashi)
{
sqstack fuzhan; //运算符栈 
sqstack shuzhan; //运算数栈

char TD[20];
int data;
int a;
int b;
 
char  *ch;
char D[2];
char e;
int fu;

chushihua(&fuzhan);
push(&fuzhan,'#');
chushihua(&shuzhan);

ch = biaodashi;
TD[0] = '\0';
while(*ch != '#' gettop(&fuzhan) != '#')
{

if(!yunsuan_fu(*ch,yunsuanfu))//不是运算符则进栈 
{
D[0] = *ch;
D[1] = '\0';
lianjie(TD,D);
ch++; 
if(yunsuan_fu(*ch,yunsuanfu))//是运算符时 
{
data = AToi(TD);
push(&shuzhan,data);
TD[0] = '\0';
}
}
else
{
switch(youxianji(gettop(&fuzhan),*ch))
{
case '<':
push(&fuzhan,*ch);
ch++;
break;
case '=':
pop(&fuzhan);

ch++;
break;
case '>':
a = pop(&shuzhan);
b = pop(&shuzhan);
fu = pop(&fuzhan);
push(&shuzhan,yunsuan(b,fu,a));
break;
}
}
}
return gettop(&shuzhan);
}
int main()
{
while(scanf("%s",str)!=EOF)
{
printf("%d\n",Biaodashi(str));
}
return 0;

}