《数据结构和算法》——逆波兰表达式
对于所求的中缀表达式，我们首先需要将其转换为后缀表达式，即将运算符写在作用的两个数的后面，然后将中缀表达式的输出作为后缀表达式计算程序的输入。在一个中缀表达式，我们首先需要用栈来储存级别较高的运算符，如*，（等。在栈中只允许级别较高的运算符在级别较低的运算符上面，所以当读取到级别最低级别最低的“+”和“-”时就将栈中的运算符弹出至“（”或栈为空，“（”可以在任何运算符下面，一旦检测到“）”立刻将栈中的运算符弹出，至“（”的位置。当检测到“*”和“/”时则压入栈中。当输入完毕后将栈中所有符号弹出。
附上计算中缀表达式的算法：
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<iostream>
using namespace std;
typedef double elem;
class stack1
{
public:
elem *top, *base;
int stack_size;
};
class stack2
{
public:
char *top, *base;
int stack_size;
};
void Initial(stack1 *s)
{
s->base = new elem;
s->top = s->base;
s->stack_size = 0;
}
void Initial(stack2 *s)
{
s->base = new char;
s->top = s->base;
s->stack_size = 0;
}
void Push(stack1 *s,elem e)
{
*(s->base) = e;
s->base++;
s->stack_size++;
}
void Push(stack2 *s, char e)
{
*(s->base) = e;
s->base++;
s->stack_size++;
}
void Pop(stack1 *s,double *e)
{
s->stack_size--;
s->base--;
*e = *(s->base);
}
void Pop(stack2 *s,char *e)
{
s->base--;
s->stack_size--;
*e = *(s->base);
}
int main()
{
stack1 s;
stack2 r;
char c;
char str;
elem d;
Initial(&s);
Initial(&r);
printf("输入要计算的中缀表达式(以#结束，数字与符号之间用空格隔开)：");
scanf_s("%c", &c);
while (c!= '#')
{
int i = 0;
while (isdigit(c) || c == '.')
{
str = c;
str = 0;
scanf_s("%c", &c);
if (i >= 20)printf("wrong,out of the limit!");
if (c == ' ')
{
d = atof(str);
Push(&s, d);
}
}
if (')' == c)
{
char e;
do
{
Pop(&r, &e);
double a, b;
switch (e)
{
case '+':
Pop(&s,&b);
Pop(&s,&a);
Push(&s, a + b);
break;
case '-':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a - b);
break;
case '*':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a * b);
break;
case '/':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a / b);
break;
}
} while (r.stack_size&&'(' != e);
}
else if (c == '+' || c == '-')
{
if (r.stack_size != 0)
{
char e;
do
{
Pop(&r, &e);
if ('(' == e)
{
Push(&r, e);
break;
}
double a, b;
switch (e)
{
case '+':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a + b);
break;
case '-':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a - b);
break;
case '*':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a * b);
break;
case '/':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a / b);
break;
}
} while (r.stack_size != 0 && e != '(');
Push(&r, c);
}
else if (r.stack_size == 0)
{
Push(&r, c);
}
}
else if ('*' == c || '/' == c||'('==c)
{
Push(&r, c);
}
scanf_s("%c", &c);
}
while (r.stack_size != 0)
{
char e;
double a, b;
Pop(&r, &e);
switch (e)
{
case '+':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a + b);
break;
case '-':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a - b);
break;
case '*':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a * b);
break;
case '/':
Pop(&s, &b);
Pop(&s, &a);
Push(&s, a / b);
break;
}
}
Pop(&s,&d);
printf("answer is %.2f\n", d);
system("PAUSE");
}
页:
[1]