给定一个字符串描述的算术表达式，计算出结果值。
输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。
数据范围：运算过程中和最终结果均满足 
，即只进行整型运算，确保输入的表达式合法
[编程题]表达式求值
func main() {
scanner := bufio.NewScanner(os.Stdin)
for scanner.Scan() {
str := scanner.Text()
res := compute(str)
fmt.Println(res)
}
}
func compute(str string) int {
// 为了能处理最后一个数字计算，就增加一个字符做最后一轮计算
str += " "
var sign byte = '+'
num := 0
nums := make([]int, 0)
for i := 0; i < len(str); i++ {
if str[i] >= '0' && str[i] <= '9' {
num = num*10 + int(str[i]-'0')
} else if str[i] == '(' {
count := 0
j := i
for {
if str[j] == '(' {
count++
} else if str[j] == ')' {
count--
if count == 0 {
break
}
}
j++
}
num = compute(str[i+1 : j])
i = j
} else {
switch sign {
case '+':
nums = append(nums, num)
case '-':
nums = append(nums, -num)
case '*':
nums[len(nums)-1] *= num
case '/':
nums[len(nums)-1] /= num
}
sign = str[i]
num = 0
}
}
res := 0
for _, v := range nums {
res += v
}
return res
}
发表于 2024-03-04 18:02:10
回复(0)
中缀表达式转后缀表达式
package main
import (
"fmt"
"strconv"
"strings"
"unicode"
)
func main() {
var s string
fmt.Scan(&s)
fmt.Println(evalRPN(infix2Postfix(split(s))))
}
func evalRPN(tokens []string) int {
var stack []int
for _, token := range tokens {
val, err := strconv.Atoi(token)
if err == nil {
stack = append(stack, val)
} else {
x, y := stack[len(stack)-2], stack[len(stack)-1]
stack = stack[:len(stack)-2]
switch token {
case "+":
x += y
case "-":
x -= y
case "*":
x *= y
case "/":
x /= y
}
stack = append(stack, x)
}
}
return stack[0]
}
// Infix notation -> Reverse Polish notation
func infix2Postfix(infix []string) (postfix []string) {
precedence := func(operator string) int {
switch operator {
case "*", "/":
return 5
case "+", "-":
return 4
}
return 0
}
var stack []string
for _, token := range infix {
switch token {
case "+", "-", "*", "/":
// 运算符，如果优先级高于栈顶元素则入栈，否则不断出栈直到符合条件
for len(stack) > 0 && precedence(stack[len(stack)-1]) >= precedence(token) {
postfix = append(postfix, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
stack = append(stack, token)
case "(":
stack = append(stack, token)
case ")":
// 弹出所有元素直到遇到左括号
for len(stack) > 0 {
if stack[len(stack)-1] != "(" {
postfix = append(postfix, stack[len(stack)-1])
stack = stack[:len(stack)-1]
} else {
// 弹出左括号
stack = stack[:len(stack)-1]
break
}
}
default:
// 操作数，直接输出
postfix = append(postfix, token)
}
}
for len(stack) > 0 {
postfix = append(postfix, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
return
}
func split(expr string) (arr []string) {
var (
start int
flag bool
prev rune
)
for i, ch := range expr {
if unicode.IsSpace(ch) || ch == '.' {
continue
}
isDigit := unicode.IsDigit(ch)
if ch == '-' {
// 使用 prev，因为 expr[i-1] 可能是空格
if i > 0 && (unicode.IsDigit(prev) || prev == ')') { // '-' 出现在数字或者 ')' 后面是减号
} else { // 负号
isDigit = true
}
}
if isDigit {
if !flag {
start = i
flag = true
}
} else {
if flag {
arr = append(arr, strings.TrimSpace(expr[start:i]))
flag = false
}
arr = append(arr, expr[i:i+1])
}
prev = ch
}
if flag {
arr = append(arr, strings.TrimSpace(expr[start:]))
}
return
}
发表于 2023-07-16 18:57:57
回复(0)
package main
import (
"bufio"
"fmt"
"os"
"strings"
"unicode"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
input := scanner.Text()
input = strings.ReplaceAll(input, "{", "(")
input = strings.ReplaceAll(input, "}", ")")
input = strings.ReplaceAll(input, "[", "(")
input = strings.ReplaceAll(input, "]", ")")
sum := calclate(input)
fmt.Println(sum)
}
func calclate(str string) int {
//存放结果
stack := []int{}
opt := '+'
num := 0
for i := 0; i < len(str); i++ {
if unicode.IsDigit(rune(str[i])) {
num = num*10 + int(str[i]-'0')
}
if str[i] == '(' {
j := i + 1
deep := 1
for deep > 0 {
if str[j] == '(' {
deep++
} else if str[j] == ')' {
deep--
}
j++
}
num = calclate(str[i+1 : j-1])
i = j - 1
}
if !unicode.IsDigit(rune(str[i])) || i == len(str)-1 {
switch opt {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
stack[len(stack)-1] *= num
case '/':
stack[len(stack)-1] /= num
}
opt = int32(str[i])
num = 0
}
}
sum := 0
for _, v := range stack {
sum += v
}
return sum
}
发表于 2022-06-08 16:34:53
回复(0)
package main
import "fmt"
func main(){
var expression string
fmt.Scanln(&expression)
fmt.Println(calculate(expression))
}
func calculate(s string)int{
stack := []int{} // 一个栈存储所有计算过的数字
var sign byte = '+'
var num int
for i := 0; i < len(s); i ++{
c := s[i]
if c == ' '{
continue
}else if isDigit(c){
num = num * 10 + int(c - '0')
}else if c == '('{
// 向后找到配对的右括号
j := i + 1
count := 1 // 记录出现过的左括号数量
for count > 0{
if s[j] == ')'{
count --
}else if s[j] == '('{
count ++
}
j ++
}
// 找出括号范围后递归求内部表达式的结果
num = calculate(s[i+1:j-1])
i = j - 1
}else if c == ')'{
continue
}
if !isDigit(c) || i == len(s)-1{
if sign == '+'{
stack = append(stack, num)
}else if sign == '-'{
stack = append(stack, -num)
}else if sign == '*'{
stack[len(stack)-1] *= num
}else if sign == '/'{
stack[len(stack)-1] /= num
}
sign = c
num = 0
}
}
ans := 0
for _, n := range stack{
ans += n
}
return ans
}
func isDigit(b byte)bool{
if b >= '0' && b <= '9'{
return true
}
return false
}
发表于 2022-05-21 23:51:30
回复(0)
package main
import (
"bufio"
"os"
"fmt"
"strings"
"strconv"
"unicode"
)
func main(){
var params []string
input := bufio.NewScanner(os.Stdin)
for input.Scan(){
params = append(params, input.Text())
}
for loop:= 0; loop< len(params); loop++{
tmp := strings.Replace(strings.Replace(params[loop], "]", ")", -1), "[", "(", -1)
tmp = strings.Replace(strings.Replace(tmp, "}", ")", -1), "{", "(", -1)
res := OutPrint(tmp)
fmt.Println(res)
}
}
func OutPrint(s string) int {
bytes := make([]byte, len(s))
copy(bytes, s)
return subCal(&bytes)
}
func subCal(bytes *[]byte) int {
stack := []int{}
num := 0
var sigh byte = '+'
for len(*bytes) > 0 {
item := (*bytes)[0]
*bytes = (*bytes)[1:]
if unicode.IsDigit(rune(item)) {
val, _ := strconv.Atoi(string(item))
num = num*10 + val
}
if item == '(' {
num = subCal(bytes)
}
if (!unicode.IsDigit(rune(item)) && item != ' ') || len(*bytes) == 0 {
switch sigh {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
num *= stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, num)
case '/':
num = stack[len(stack)-1]/num
stack = stack[:len(stack)-1]
stack = append(stack, num)
}
sigh = item
num = 0
}
if item == ')' {
break
}
}
sum := 0
for i := 0; i < len(stack); i++ {
sum += stack[i]
}
return sum
}
发表于 2021-10-25 18:31:22
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
