LeetCode224. Basic Calculator (用栈计算表达式)

解题思路

用两个栈分别存字符和数字。
顺序读入字符，处理方式分为字符和数字两种。
处理字符分为')'和非')'两种。
处理数字需要读取字符栈栈顶，分为'+'、'-'和非'+'、'-'。

代码

class Solution {

public:

    stack <int> st;//数字栈

    stack <char> cst;//符号栈

    void solveNum(int n){

        //如果碰到加减，将上一个数字取出来，做运算之后放入栈中

        if(st.size() &&cst.size()){

            char c = cst.top();

            if(c == '+'){

            	cst.pop();

           		int t = st.top();

            	st.pop();

                st.push(t+n);

            }else if(c == '-'){

            	cst.pop();

            	int t = st.top();

            	st.pop();

                st.push(t-n);

            }else{

                st.push(n);

            }

        } else{

            st.push(n);

		}

    }

    //处理字符

    void solveChar(char c){

        //如果遇到')'，弹出'('即可，并且处理顶部数字,应对类似1+(1+1)+2的情况

        if(c != ')'){

            cst.push(c);

		}else{

            cst.pop();

            if(st.size()){

            	int t = st.top();

            	st.pop();

            	solveNum(t);

			}

		}

    }

    int calculate(string s) {

        //加上“（）”是为了避免全字符的情况

    	s += "()";

        int num = 0;

        int flag = 0;

		for(auto i:s){

            if(i == ' ') continue;

            if(i >= '0' && i <= '9') num = num*10+i-'0', flag = 1;

            else{

                //如果上一个字符是数字

            	if(flag == 1){

                    //处理数字

            		solveNum(num);

            		num = 0;

            		flag = 0;

				}

                //处理字符

				solveChar(i);

			}

        }

        return st.top();

    }

};

巴特西

LeetCode224. Basic Calculator (用栈计算表达式)

解题思路

代码

最新文章

热门文章