Basic Calculator
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
.
Example 1:
Input: "1 + 1" Output: 2
Example 2:
Input: " 2-1 + 2 " Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)" Output: 23Note:
- You may assume that the given expression is always valid.
- Do not use the
eval
built-in library function.
Solution(javascript)
/** 括号会影响运算顺序, 不能直接去括号
* @param {string} s
* @return {number}
*/
const calculate = function (s) {
const help = xs => xs.reduce((acc, item, index) => {
if (item === '-') {
xs[index + 1] = -xs[index + 1]
return acc
} if (item === '+') {
return acc
}
return acc + item
}, 0)
const stack = []
let current = ''
for (const c of s) {
// 去空格,组合数字
if (c === '-' || c === '+' || c === '(' || c === ')') {
if (current !== '') {
stack.push(parseInt(current, 10))
current = ''
}
stack.push(c)
} else if (c === ' ') {
if (current !== '') {
stack.push(parseInt(current, 10))
current = ''
}
} else {
current += c
}
// 去括号
while (stack[stack.length - 1] === ')') {
stack.pop()
const temp = []
while (stack[stack.length - 1] !== '(') {
temp.push(stack.pop())
}
stack.pop()
stack.push(
help(temp.reverse()),
)
}
// console.log(c, stack)
}
if (current !== '') {
stack.push(parseInt(current, 10))
}
return help(stack)
}