• 26.0%

https://leetcode.com/problems/basic-calculator/?tab=Description

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.

Note: Do not use the eval built-in library function.

https://discuss.leetcode.com/topic/22359/16-ms-solution-in-c-with-stacks

16 ms solution in C++ with stacks

26ms, September 13, 2016

https://discuss.leetcode.com/topic/15806/easy-18-lines-c-16-lines-python

Easy 18 lines C++, 16 lines Python

Keep a global running total and a stack of signs (+1 or -1), one for each open scope. The “global” outermost sign is +1.

• Each number consumes a sign.
• Each + and - causes a new sign.
• Each ( duplicates the current sign so it can be used for the first term inside the new scope. That’s also why I start with [1, 1] - the global sign 1 and a duplicate to be used for the first term, since expressions start like 3… or (…, not like +3… or +(….
• Each ) closes the current scope and thus drops the current sign.

Also see the example trace below my programs.

C++:

Python:

Example trace:

If you want to see traces for other examples, you can add this at the start inside the loop and after the loop (that’s for the Python solution, where it’s all easier):

https://discuss.leetcode.com/topic/15775/simple-c-in-24-ms

Simple c++ in 24 ms

python

https://discuss.leetcode.com/topic/25775/python-concise-solution-with-stack

Python concise solution with stack.

https://discuss.leetcode.com/topic/37951/python-with-stack

Python with stack

This solution uses stack to store previous result and sign when encounter a “(“

For this problem storing sign is enough, and will be faster.

https://discuss.leetcode.com/topic/15932/ac-python-solution

AC Python Solution

java

https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack

Iterative Java solution with stack

Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.

Only 5 possible input we need to pay attention:

1. digit: it should be one digit from the current number
2. ‘+’: number is over, we can add the previous number and start a new number
3. ‘-‘: same as above
4. ‘(‘: push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
5. ‘)’: pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.

Finally if there is only one number, from the above solution, we haven’t add the number to the result, so we do a check see if the number is zero.

https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack/2

+1 for your concise and clean code. My solution seems to be really different from others.
First I reformed the input expression by rules of:

1. remove all ‘(‘, ‘)’, ‘ ‘;
2. reverse the express string;
3. add ‘+’ or ‘-‘ to the end of the express.
By this approach, the reformed expression will be easy to handled.

Java code:

https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand

JAVA———–Easy Version To Understand!!!!!

java

28ms, September 13, 2016

https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand