1.表达式的计算
主要考察栈的一些运用
先加减，后乘除，有括号先算，无需多讲；
------------------------------------------------------------------------------------------------------
遇到数字入（收集数据）push_data,
（与运算符先比较优先级高入栈，低的话出栈运算并把数据入栈--
直到遇到比他高一级的运算符或者elem已空）最后push_elem,；；；
遇到‘（’入elem; ‘)‘那就将括号里面的运算
把剩下的做运算结果存入整型数组的第一个
-----------------------------------------------------------------------------------------------------
废话不多说，直接上代码！！！！
--------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
//#define _OJ_
//#define maxsize 100
typedef struct stack1
{
char *elem;
float *data;
int top; int top1;
int base; int base1;
} stack1, *stack;
stack
creat_stack(void)
{
stack s;
s = (stack) malloc (sizeof(stack1));
s->elem = (char*) malloc (100 * sizeof(char));
s->data = (float*) malloc (100 * sizeof(float));
s->top = s->base = 0;
s->top1 = s->base1 = 0;
return s;
}
float
data_pop(stack s)
{
return s->data[--s->top];
}
char
elem_pop(stack s)
{
return s->elem[--s->top1];
}
void
push_data(stack s, float x)
{
s->data[s->top++] = x;
}
void
push_elem(stack s, char ch)
{
s->elem[s->top1++] = ch;
}
int
data_isempty(stack s)
{
if(s->top == s->base)
return 1;
else
return 0;
}
int
elem_isempty(stack s)
{
if(s->top1 == s->base1)
return 1;
else
return 0;
}
char
gettop(stack s)
{
return s->elem[s->top1 - 1];
}
float
gettop1(stack s)
{
return s->data[s->top - 1];
}
float
operater(float a, char op, float b)
{
switch (op) {
case ‘+‘: return a + b;
case ‘-‘: return a - b;
case ‘*‘: return a * b;
case ‘/‘: return a / b;
}
}
int
get_rank(char op)
{
switch (op) {
case ‘+‘:
case ‘-‘: return 1;
case ‘*‘:
case ‘/‘: return 2;
case ‘(‘: return 3;
}
}
//建立一个字符数组和整型数组分别记录
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
char ch1;
char str2[100];
char str[50];
double data2, data1, data, n, f;
int rank1, rank2, T, i = 0, j = 0, l1 = 0;
stack s;
scanf("%d", &T);
while(T--){
scanf("%s", str);
i = 0;
s = creat_stack();
if(str[0] == ‘0‘ && str[1] == ‘\0‘) break;//遇到零就结束
if(str[0] != ‘0‘ && str[1] == ‘\0‘) {printf("%c\n", str[0]); continue;}
//只有你一个数那么就输出
while (str[i] != ‘=‘) {
data = 0; j = 0;
for(l1 = 0;l1 < 50; l1++)
str2[l1] = 0;
if (‘0‘ <= str[i] && str[i] <= ‘9‘) {
while((‘0‘ <= str[i] && str[i] <= ‘9‘) || (str[i] == ‘.‘)) {
str2[j++] = str[i];
i++;
}
f = atof(str2);//将数值以字符型存入一个数组里面，用atof将其转化为浮点数
push_data(s,f);//收集数据传入data数组
continue;
}
else if(str[i] == ‘(‘)
push_elem(s,str[i]);
else if(str[i] == ‘)‘) {//遇右括号就把里面的数计算入栈
while (gettop(s) != ‘(‘) {
data1 = data_pop(s); data2 = data_pop(s);
ch1 = elem_pop(s);
n = operater(data2,ch1,data1);
push_data(s,n);
}
elem_pop(s);
}
else{
if(elem_isempty(s)) push_elem(s,str[i]);//先判断栈是否为空空的就入栈
else {
ch1 = gettop(s); rank1 = get_rank(ch1);
rank2 = get_rank(str[i]);
while ((ch1 != ‘(‘) && (rank2 <= rank1) && elem_isempty(s) != 1) {
ch1 = gettop(s);
if(ch1 == ‘(‘) break;//注意不可和（作比较
data1 = data_pop(s); data2 = data_pop(s);
ch1 = elem_pop(s);
n = operater(data2,ch1,data1);
push_data(s,n);
}//把优先级别高的和相等的计算入栈
push_elem(s,str[i]);
}
}
i++;
}
//把剩下的做运算结果存入整型数组的第一个
while (!elem_isempty(s)) {
data1 = data_pop(s); data2 = data_pop(s);
ch1 = elem_pop(s);
n = operater(data2,ch1,data1);
push_data(s,n);
}
int f1;
f1 = int(gettop1(s));
if(f1 == gettop1(s))
printf("%d\n", f1);
else
printf("%.2lf\n", gettop1(s));
// 利用其原理可以做一个计算器,如果计算之结果是整数就输出整数
// 否则就输出浮点数
}
// printf("%d\n", ‘\0‘);
return 0;
}
// 1.000+2/4=
// ((1+2)*5+1)/4=
原文：http://www.cnblogs.com/airfand/p/4996123.html