中缀表达式求值

开两个栈：数据栈和符号栈，前者存储数值，后者存储操作符。
操作符优先级：+-优先级相同，*/优先级相同，后者优先级大于前者优先级。
扫描中缀表达式：
    如果是数值，则压入数据栈
    如果是符号：
        如果符号栈为空：
            直接压入符号栈
        否则：
            如果当前符号的优先级比符号栈栈顶符号的优先级高：
                直接压入符号栈
            否则：
                从数据栈取两个操作数
                从符号栈取一个符号
                计算运算结果并压入符号栈
                循环直到符号栈为空，或者当前符号优先级比符号栈栈顶符号的优先级高
                当前符号压入符号栈
    如果符号栈不为空：
        从数据栈取两个操作数
        从符号栈取一个符号
        计算运算结果并压入符号栈
    输出结果

测试地址：

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

char op[256] = {0};

void init()
{
    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;
}

double calc(double x, double y, char op)
{
    if (op == '+') return x + y;
    if (op == '-') return x - y;
    if (op == '*') return x * y;
    return x / y;
}

int main(int argc, char **argv)
{
    init();
    stack<double> values;
    stack<char> ops;
    char s[210];

    while (1)
    {
        gets(s);
        int n = strlen(s);
        if (n == 1 && s[0] == '0')
        {
            break;
        }

        double tmp = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                tmp = tmp*10 + s[i]-'0';
            }
            else if (s[i] == ' ')
            {
                values.push(tmp);
                tmp = 0;
            }
            else
            {
                int cur = op[s[i]];
                int pre = 0;
                if (!ops.empty())
                {
                    pre = op[ops.top()];
                }
                while (cur <= pre)
                {
                    double right = values.top();
                    values.pop();
                    double left = values.top();
                    values.pop();
                    char _op = ops.top();
                    ops.pop();
                    values.push(calc(left, right, _op));

                    if (!ops.empty())
                    {
                        pre = op[ops.top()];
                    }
                    else
                    {
                        break;
                    }
                }
                ops.push(s[i]);
                ++i;
                tmp = 0;
            }
        }
        values.push(tmp);

        while (!ops.empty())
        {
            double right = values.top();
            values.pop();
            double left = values.top();
            values.pop();
            char _op = ops.top();
            ops.pop();
            values.push(calc(left, right, _op));
        }
        printf("%.2f\n", values.top());
    }

    return 0;
}

对于存在括号的情况，考虑一下括号即可：

中缀表达式转后缀表达式

算法： 可以使用栈来完成中缀表达式到后缀表达式的转换

1、栈stack[]用来存储操作符，top指向栈顶，但不存储元素，top=0表示栈为空

2、从左向右遍历中缀表达式

　　a.如果遇到的是操作数num，则直接输出到后缀表达式

　　b.如果遇到的是操作符op，则有几种情况：

　　　　b.1.如果op==')'，则依次弹出栈顶直到弹出'('，但'('不输出到后缀表达式

　　　　b.2:如果op=='('，则直接入栈

　　　　b.3:如果栈为空，则直接入栈

　　　　b.4:如果op的优先级高于栈顶操作符的优先级，则入栈

　　　　b.5:如果op的优先级低于或等于栈顶操作符的优先级，则依次弹出栈顶直到op的优先级高于栈顶操作符的优先级（或栈为空），再将op入栈

3、遍历完时，如果栈仍不为空，则依次弹出栈顶直到栈为空

参考：http://www.cnblogs.com/zghaobac/p/3394705.html