问题
计算无括号算术表达式的值
问题分析
运算符优先级:
设置#代表表达式结束标志。
| 符号 | 符号 | 符号 |
|---|---|---|
| +- | */ | ** |
| 0 | 1 | 3 |
算法原理：
例如：1+1*2
设置两个栈：number(运算数栈)、symbol(运算符栈)
对输入的字符自左向右扫描，进行如下处理：
遇到运算数则进number栈；
遇到运算符则与symbol栈的栈顶元素进行优先级比较：
若栈顶元素的优先级大于当前符号的优先级，则symbol退栈一次，的得到运算符，number栈退栈两次，得到两个运算数，将计算结果压入栈中。再将当前符号压入栈中。
否则，直接将符号压入栈中。
实现
Node
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkStack
{
class Node<T>
{
T data;
Node<T> next;
/// <summary>
/// 构造器
/// </summary>
public Node()
{
this.Data = default(T);
this.Next = null;
}
/// <summary>
/// 构造器
/// </summary>
/// <param name="data"></param>
public Node(T data)
{
this.Data = data;
}
public T Data { get => data; set => data = value; }
internal Node<T> Next { get => next; set => next = value; }
}
}
LinkStack
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkStack
{
class LinkStack<T>
{
Node<T> top;
public LinkStack()
{
this.top = new Node<T>();
}
/// <summary>
/// 入栈
/// </summary>
/// <param name="data"></param>
public void Push(T data)
{
//新建节点
Node<T> tmp = new Node<T>(data);
//挂载节点
tmp.Next = this.top.Next;
this.top.Next = tmp;
}
/// <summary>
/// 出栈
/// </summary>
/// <returns></returns>
public T Pop()
{
if (top.Next == null) return default(T);
//保存栈顶节点
Node<T> tmp = top.Next;
//悬空栈顶节点
top.Next = top.Next.Next;
return tmp.Data;
}
/// <summary>
/// 判空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (this.top.Next == null) return true;
return false;
}
/// <summary>
/// 读栈顶
/// </summary>
/// <returns></returns>
public T ReadTop()
{
return top.Next.Data;
}
}
}
Program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
namespace LinkStack
{
class Program
{
static void Main(string[] args)
{
LinkStack<int> number = new LinkStack<int>();
LinkStack<string> symbol = new LinkStack<string>();
string input = Console.ReadLine();
string numberTmp = "";
string symbolTmp = "";
Regex regex = new Regex(@"[0-9]");
//遍历如果是数字，则缓存，当不是数字时，将缓存入栈并清空缓存
for (int i = 0; i < input.Length; i++)
{
//输入数字
if (regex.IsMatch(input[i] + ""))
{
//缓存数字
numberTmp += input[i];
//高优先级计算
if (!symbol.IsEmpty() && SymbolMatch(symbol.ReadTop(), symbolTmp))
{
int num1 = number.Pop();
int num2 = number.Pop();
number.Push(Calculate(num1,num2,symbolTmp));
}
//符号入栈
if (!symbolTmp.Equals(""))
{
symbol.Push(symbolTmp);
}
symbolTmp = "";
}
else if (input[i]!='#')
//输入符号
{
string s = input[i] + "";
symbolTmp += s;
//数字入栈
number.Push(int.Parse(numberTmp));
numberTmp = "";
}else
{
number.Push(int.Parse(numberTmp));
int total = 0;
while (!symbol.IsEmpty())
{
total += Calculate(number.Pop(), number.Pop(), symbol.Pop());
}
Console.WriteLine(total);
}
}
}
/// <summary>
/// 符号优先级判断
/// </summary>
/// <param name="s1"></param>
/// <param name="s2"></param>
/// <returns></returns>
static bool SymbolMatch(string s1, string s2)
{
Dictionary<string, int> dic = new Dictionary<string, int>() {
{ "*",2},
{ "/",2},
{ "+",1},
{ "-",1},
{ "#",0}
};
return dic[s1] > dic[s2];
}
/// <summary>
/// 计算
/// </summary>
/// <returns></returns>
static int Calculate(int num1,int num2,string symbol)
{
int num=0;
switch (symbol)
{
case "*":
num= num1 * num2;
break;
case "/":
num= num1 / num2;
break;
case "+":
num= num1 + num2;
break;
case "-":
num= num1 - num2;
break;
}
return num;
}
}
}
网友评论