栈操作的问题 - c++编程基础

TOP

栈操作的问题

2016-12-28 08:15:43 【大中小】浏览:266次

题意：给出一个表达式，包含运算符+,-,*，min,max，求其结果

思路：用两个栈，一个操作数栈，一个操作符栈，当处理+,-,*操作符时，如果处理的操作符优先级比栈顶操作符优先级低，就入栈，否则，出栈；在处理min,max操作符时，如果当前处理的为min或者max,将min或者max,(两个入栈，当处理逗号时，就出栈，直到栈顶操作符为左括号，并将逗号入栈；而当处理右括号时，出栈直到栈顶为逗号。当处理完毕后，操作符栈可能不为空，需要出栈处理

代码如下：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
  
using namespace std;  
  
const int MAX_LEN = 100;  
  
class Solution  
{  
public:  
    int Calculate(char *pszExpr)  
    {  
        map pPriority;  
        pPriority["+"] = 1;  
        pPriority["-"] = 1;  
        pPriority["*"] = 2;  
        pPriority["("] = 0;  
  
        stack operStack;  
        stack numStack;  
  
        int len = strlen(pszExpr);  
  
        for (int i = 0; i < len; i++)  
        {  
            if (isspace(pszExpr[i])) continue;  
  
  
            //数字  
            if (isdigit(pszExpr[i]))  
            {  
                int j = i;  
                int sum = 0;  
                while (j < len && isdigit(pszExpr[j]))  
                {  
                    sum = sum * 10 + (pszExpr[j] - '0');  
                    j++;  
                }  
                numStack.push(sum);  
                i = j - 1;  
                continue;  
            }  
  
            if (pszExpr[i] == '-' || pszExpr[i] == '+' || pszExpr[i] == '*')  
            {  
                if (operStack.empty())  
                {  
                    string tmp;  
                    tmp += pszExpr[i];  
                    operStack.push(tmp);  
                }  
                else  
                {  
                    string curOper;  
                    curOper += pszExpr[i];  
                    if (pPriority[curOper] > pPriority[operStack.top()])  
                    {  
                        operStack.push(curOper);  
                    }  
                    else  
                    {  
                        while(!operStack.empty() && pPriority[curOper] <= pPriority[operStack.top()])  
                        {  
                            int ans = popCal(numStack, operStack);  
                            numStack.push(ans);  
                        }  
                        operStack.push(curOper);  
                    }  
                }  
            }  
            else if (pszExpr[i] == 'm')  
            {  
                char tmp[4] = { 0 };  
                strncpy(tmp, &pszExpr[i], 3);  
                string strtmp = tmp;  
                operStack.push(strtmp);  
                operStack.push("(");  
                i += 3;  
                continue;  
            }  
            else if (pszExpr[i] == ',')  
            {  
                while (!operStack.empty() && operStack.top() != "(")  
                {  
                    int ans = popCal(numStack, operStack);  
                    numStack.push(ans);  
                }  
                operStack.push(",");  
            }  
            else if (pszExpr[i] == ')')  
            {  
                while (!operStack.empty() && operStack.top() != ",")  
                {  
                    int ans = popCal(numStack, operStack);  
                    numStack.push(ans);  
                }  
                operStack.pop();//弹出,  
                operStack.pop();//弹出(  
                int ans = popCal(numStack, operStack);  
                numStack.push(ans);  
            }  
        }  
  
        while (!operStack.empty())  
        {  
            int ans = popCal(numStack, operStack);  
            numStack.push(ans);  
        }  
  
        return numStack.top();  
    }  
  
private:  
    int cal(int num1, int num2, string oper)  
    {  
        if (oper == "+")  
        {  
            return num1 + num2;  
        }  
        else if (oper == "-")  
        {  
            return num1 - num2;  
        }  
        else if (oper == "*")  
        {  
            return num1 * num2;  
        }  
        else if (oper == "min")  
        {  
            return min(num1, num2);  
        }  
        else if (oper == "max")  
        {  
            return max(num1, num2);  
        }  
    }  
  
    int popCal(stack& numstack, stack& operstack)  
    {  
        int num2 = numstack.top(); numstack.pop();  
        int num1 = numstack.top(); numstack.pop();  
        string op = operstack.top(); operstack.pop();  
        int ans = cal(num1, num2, op);  
  
        return ans;  
    }  
};

验证代码如下：

1 * 2 + max(3,4)

min(2+3, max(4, 5))

int main()  
{  
#ifndef ONLINE_JUDGE  
    ifstream fin("f:\\oj\\uva_in.txt");  
    streambuf *old = cin.rdbuf(fin.rdbuf());  
#endif  
    Solution solver;  
    char s[MAX_LEN];  
    while (cin.getline(s, MAX_LEN))  
    {  
        cout << "s:" << s << endl;  
        int ans = solver.Calculate(s);  
        cout << "ans:" << ans << endl;  
    }  
#ifndef ONLINE_JUDGE  
    cin.rdbuf(old);  
#endif  
    return 0;  
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：3----结构体中使用柔性数组	下一篇：C++读取硬盘序列号