数据结构-表达式求值（C++）

解题思路:

注意事项:

参考代码:

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int cal(string exp) 

{

    stack<int> numb;

    stack<char> oper;

    for (int i = 0; i < exp.length(); i++) 

    {     //if (isdigit(exp[i]))

          //{

          //    int num = exp[i] - '0';

          //    numb.push(num);

          //}弊端是只能处理个位数

        if (isdigit(exp[i])) 

        {

            int num = 0;

            while (i < exp.length() && isdigit(exp[i])) 

            {

                num = num * 10 + (exp[i] - '0');

                i++;//数字字符是一个一个检测百位数字从个位开始累加

            }

            numb.push(num);

            i--;//因此到这里不用担心不够减

        }

        else if (exp[i] == '(') 

        {

            oper.push(exp[i]);

        }

        else if (exp[i] == ')') 

        {

            while (!oper.empty() && oper.top() != '(') 

            {

                int op2 = numb.top();

                numb.pop();

                int op1 = numb.top();

                numb.pop();

                char op = oper.top();

                oper.pop();

                if (op == '+') {

                    numb.push(op1 + op2);

                }

                else if (op == '-') {

                    numb.push(op1 - op2);

                }

                else if (op == '*') {

                    numb.push(op1 * op2);

                }

                else if (op == '/') {

                    numb.push(op1 / op2);

                }

            }

            oper.pop(); // 弹出 '('

        }

        else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') 

        {

            while (!oper.empty() && oper.top() != '(' && (oper.top() == '*' || oper.top() == '/'))

            {

                int op2 = numb.top();

                numb.pop();

                int op1 = numb.top();

                numb.pop();

                char op = oper.top();

                oper.pop();

                if (op == '+') {

                    numb.push(op1 + op2);

                }

                else if (op == '-') {

                    numb.push(op1 - op2);

                }

                else if (op == '*') {

                    numb.push(op1 * op2);

                }

                else if (op == '/') {

                    numb.push(op1 / op2);

                }

            }

            oper.push(exp[i]);

        }

    }

    while (!oper.empty()) //这段代码的存在的意义就是进行一些简单的加减法

    {//因为上面的while循环把+ - 直接筛选掉了 没有到乘除是进不去的

        int op2 = numb.top();

        numb.pop();

        int op1 = numb.top();

        numb.pop();

        char op = oper.top();

        oper.pop();

        if (op == '+') {

            numb.push(op1 + op2);

        }

        else if (op == '-') {

            numb.push(op1 - op2);

        }

        else if (op == '*') {

            numb.push(op1 * op2);

        }

        else if (op == '/') {

            numb.push(op1 / op2);

        }

    }

    return numb.top();

}

int main() {

    string exp;

    while (getline(cin, exp)) 

    {

        if (exp == "#")

            break;

        int result = cal(exp);

        cout << result << endl;

    }

    return 0;

}