面试题 16.26.计算器

1. 题目描述

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数， + ， - ， * ， / 四种运算符和空格 `` 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。
• 请 不要 使用内置的库函数 eval 。

标签 栈 数学 字符串

2. 解题

使用两个栈，一个数字栈，一个符号栈.

• 遇数字，则进数字栈
• 遇运算符
  • 当前运算符优先级大于栈顶运算符优先级，入栈
  • 当前运算符优先级小于栈顶运算符优先级，取出数字栈顶两个数字与符号栈顶符号，numStack[-2] op numStack[-1]，结果入数字栈
• 字符串结束，则依次取出数字栈与符号栈进行运算，运算结果放回数字栈。