leetcode-Basic Calculator

2019-11-06 07:19:39

字体：大中小

来源：转载

供稿：网友

Question:

Implement a basic calculator to evaluate a simple exPRession string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

“1 + 1” = 2 ” 2-1 + 2 ” = 3 “(1+(4+5+2)-3)+(6+8)” = 23

Solution:

class Solution {public: int calculate(string s) { char stack1[100000]; int stack2[100000]; int top1 = -1; int top2 = -1; s += '#'; int len = s.size(); for( int i = 0 ; i < len ; i++ ){ switch(s[i]){ case ' ':break; case '(':stack1[++top1] = '(';break; case ')':{ if(stack1[top1] == '('){ top1--; break; } switch(stack1[top1--]){ case '+': stack2[top2-1] = stack2[top2] + stack2[top2-1]; break; case '-': stack2[top2-1] = stack2[top2-1] - stack2[top2]; break; } top2--; top1--; } break; case '+': case '-': case '#': if(top1 >= 0 && stack1[top1] != '('){ switch(stack1[top1]){ case '+': stack2[top2-1] = stack2[top2] + stack2[top2-1]; top2--; break; case '-': stack2[top2-1] = stack2[top2-1] - stack2[top2]; top2--; break; } top1--; } stack1[++top1] = s[i]; break; default: int tmp = s[i] - 48; while(i<len && s[i+1]>='0' && s[i+1]<='9'){ tmp = tmp*10 + s[++i]-48; } stack2[++top2] = tmp; } } return top2==0?stack2[0]:0; }};

总结：

声明两个栈，一个栈存数字，另一个存储操作符，保证栈顶操作符优先级最大。如果栈顶操作符优先级高于将要入栈的操作符，就先将栈顶操作符A出栈，从数据栈中弹出两个数x1，x2，将x1 A x2的结果存于数据栈顶，直至栈顶操作符优先级低于将要入栈的操作符。遍历完输入表达式后，判断数据栈只有一个数，并且操作符栈为空，否则，输入表达式出错。操作符优先级高->低：（ */ +- ），其中‘）’不入栈，并且遇到栈顶为‘（’时，弹出‘（’。

小技巧：给表达式添加结束符’#‘可以使问题简化。

上一篇：template模板及模板类的实例化

下一篇：微信红包>200发放